今天的第二波到了，大伙接住喽

teebye

人民币按面值有（1毛，5毛，1元，5元，10元，20元，50元，100元）共8种；
现在需要支付100元钱，问总共有多少种支付组合？ 打印出这些组合？
比如，10个10元就是一种，2个50元又是另一种，甚至1000个1毛也是一种。

zhenglxd

原帖由 teebye 于 2009-3-23 10:26 发表
人民币按面值有（1毛，5毛，1元，5元，10元，20元，50元，100元）共8种；
现在需要支付100元钱，问总共有多少种支付组合？ 打印出这些组合？
比如，10个10元就是一种，2个50元又是另一种，甚至1000个1毛也是一种。

命题太大了
10个一毛+99个一元是不是还算一种啊。。
20个一毛+98个一元是不是也算一种呢。。

teebye

当然算啊

daybreakcx

def calc(list,pos,cursum,allsum,use):     if (pos==len(list)-1):         if ((allsum-cursum)%list[pos]==0):             use[pos]=int((allsum-cursum)/list[pos])             print(use)     else:         for use[pos] in range(int((allsum-cursum)/list[pos])+1):             cursum=cursum+use[pos]*list[pos]             calc(list,pos+1,cursum,allsum,use)             cursum=cursum-use[pos]*list[pos] list=[1,5,10,50,100,200,500,1000] use=[0,0,0,0,0,0,0,0] calc(list,0,0,1000,use)

献丑了，因为几毛钱显示的不爽就把1毛当作单位1，list就是那个列表，use就表示当前使用情况，递归输出，效率不算高，情况数太多，我是用3.0的，因此print用了括号

[ 本帖最后由 daybreakcx 于 2009-3-23 12:39 编辑 ]

teebye

你算下的结果是多少？

daybreakcx

因为递归层数多，程序有点卡，不便算结果，我用动态规划可以得到一个结果是400189，不过是用C算的，哈哈

#include<stdio.h> #include<string.h> int use[8]={1,5,10,50,100,200,500,1000},last[1001],res[1001],i,j,k; int main() { &nbsp;&nbsp;&nbsp;&nbsp;memset(res,0,sizeof(res)); &nbsp;&nbsp;&nbsp;&nbsp;last[0]=res[0]=1; &nbsp;&nbsp;&nbsp;&nbsp;for (i=0;i<8;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for (j=0;j<=1000;j++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (last[j]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for (k=use[i];j+k<=1000;k+=use[i]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j+k]+=last[j]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memcpy(last,res,sizeof(res)); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;printf("%d\n",res[1000]); &nbsp;&nbsp;&nbsp;&nbsp;return 0; }

[ 本帖最后由 daybreakcx 于 2009-3-23 12:39 编辑 ]

izhier

这不是相当于解八元一次方程吗

1. 
   
2. 0.1a + 0.5b + 1c + 5d + 10e + 20f + 50g + 100h = 100
   
3. a,b,c,d,e,f,g,h属于非负数
   

复制代码

daybreakcx

突然发现论坛里支持语法高亮的，重新编辑了一下

daybreakcx

解八元一次方程思路是对的，但是如果个数不定的话就不好解了，基本上就只剩下穷举了，当然，如果单纯是算个数的话，动态规划是完全能胜任的

teebye

400189 是正解