人民币问题

pilyfe

<P>我国现行货币面值为：1分、2分、5分、1角、2角、5角、1元、2元、5元、10元、20元、50元、100元。</P>
<P>问题是：每一张面值的人民币用比他小的面值人民币组成，共有多少种组法？</P>
<P>比如：2分有1种组法、5分有3种、1角有10种......</P>
<P>这该如何计算其他面值？</P>

魔鱼儿

应该是相同数字面值的钱随单位的变化会成几何倍数的增加吧，100元的组合可能就太多了/ 不管了，先占沙发。

kexin_xiao

抢个板凳，问一下，这个研究有什么意义吗？呵呵

nhlijiaming

如果是编程， 这就设计一个动态规划的完全背包问题 <BR>假设i元有n种取法 ， 对于每个i ，就等于 i-面值 的取法总和<BR>假设把面值数放在money[j]中， 有k种面额 ， t表示 i元有t种取法<BR>动态规划状态方程是 ： t【 i 】=t[i-money[j]]+t { 0&lt;=i , 0&lt;j&lt;k }<BR>开始时t[0]=0<BR>例题： 金银岛(coin)<BR>打得好辛苦 ..<BR>&nbsp; 这里不能用中括号括住 i&nbsp; ， 很无奈～

[ 本帖最后由 nhlijiaming 于 2008-6-2 13:26 编辑 ]

nhlijiaming

例题找不到了  ， 我记得 usaco Chapter 2 有一道题是类似的

[ 本帖最后由 nhlijiaming 于 2008-6-2 13:20 编辑 ]

nhlijiaming

终于找到了   希望没有灌水嫌疑  。。  怕不够位置<BR><BR>USACO <BR>Section 2.3<BR>Money Systems<BR><BR>The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure. <BR><BR>The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others. <BR><BR>Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal). <BR><BR>PROGRAM NAME: money<BR>INPUT FORMAT<BR>The number of coins in the system is V (1 &lt;= V &lt;= 25). <BR><BR>The amount money to construct is N (1 &lt;= N &lt;= 10,000). Line 1:  Two integers, V and N <BR> Lines 2..:  V integers that represent the available coins (no particular number of integers per line) <BR><BR><BR>SAMPLE INPUT (file money.in) <BR>3 10<BR>1 2 5<BR><BR>OUTPUT FORMAT<BR>A single line containing the total number of ways to construct N money units using V coins. <BR>SAMPLE OUTPUT (file money.out)<BR>10<BR><BR>Money Systems<BR><BR>货币系统<BR><BR>译 by timgreen<BR><BR>母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。<BR>[In their own rebellious way],，他们对货币的数值感到好奇。<BR>传统地，一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。<BR>母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。<BR>举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。<BR>写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。<BR>保证总数将会适合long long (C/C++) 和 Int64 (Free Pascal)。<BR><BR>PROGRAM NAME: money<BR><BR>INPUT FORMAT<BR><BR>货币系统中货币的种类数目是 V 。 (1&lt;= V&lt;=25)<BR>要构造的数量钱是 N 。 (1&lt;= N&lt;=10,000)<BR><BR>第 1 行:  二整数， V 和 N <BR>第 2 ..V+1行： 可用的货币 V 个整数　(每行一个　每行没有其它的数)。 <BR><BR>SAMPLE INPUT (file money.in) <BR>3 10<BR>1 2 5<BR>OUTPUT FORMAT<BR>单独的一行包含那个可能的构造的方案数。<BR>SAMPLE OUTPUT (file money.out)<BR>10<BR><BR>

gozichen

真是一样米养百样人啊，太费脑了

whitetiger

比较简单的问题“一个数字用比它小的数字之和表示有多少种情况”已经很折腾人了，这个更麻烦。等着看结论吧！

丙丙

RMB通常没有这么复杂，花完就没了

黑索金

那啥 我智商66  晕菜啊！