Chinaunix

标题: 算法题——钱币组合问题 [打印本页]
作者: 千年沉寂    时间: 2009-04-14 18:51
标题: 算法题——钱币组合问题
钱币组合问题

    问题描述：设有n 种不同的钱币各若干张，可用这n 种钱币产生许多不同的面值。试设计一个算法，计算给定的某个面值，能有多少种不同的产生方法。例如有1 分3 张，2 分3 张，5 分1 张，则能组成7 分面值的方法有：3 个1 分+2 个2 分，1 个1 分+3 个2 分，2个1 分+1 个5 分，1 个2 分+1 个5 分共四种。
    编程任务：对于给定的n 种不同钱币，编程计算某个给定面值能有多少种不同的产生方法。
作者: 千年沉寂    时间: 2009-04-14 19:22
Python实现代码：

#!/usr/bin/env python
def coin(moneylst,countlst,d):
    tmp[0] = 1
    tmp[1::1] = d * [0]
    for i in range(len(moneylst)):
        for k in range(d,-1,-1):
            if tmp[k] > 0:
                for j in range(1, countlst[i] + 1):
                    if (k + j * moneylst[i]) > d :
                        break
                    tmp[k + j * moneylst[i]] += tmp[k];
    return tmp[d]
def main():
    money = [1,2,5]
    count = [3,3,1]
    d = 7
    print coin(money,count,d)
if __name__=="__main__":
    main()
作者: wudagang0123    时间: 2009-04-18 17:42
python代码：
def func_1(n,t):
        if n == kind:
                if t == 0:
                        global ncount
                        ncount = ncount+1
                return
        for i in range(ccount[n]+1):
                if t - cvalue[n]*i >= 0:
                        func_1(n+1,t-cvalue[n]*i)
                else:
                        func_1(n+1,t)

if __name__ == '__main__':
        cvalue = [1,2,5]
        ccount = [3,3,1]
        kind = 3
        total = 7
        ncount = 0
       
        func_1(0,7)
        print ncount
作者: efhilt    时间: 2009-04-18 19:46
递归，还是递归。

碰到这种题目，应该条件反射一样地使用递归。


  2. def func(value):
  3.     coins = (1, 2, 5)
  4.     if value in coins:
  5.         yield [value, ]
  6.     elif value == 3:
  7.         yield [1, 2]
  8.     else:
  9.         for c in coins:
  10.             reministic = value -c
  11.             if reministic > 0:
  12.                 for comb in func(value - c):
  13.                     comb.insert(0, c)
  14.                     yield comb

复制代码
作者: 千年沉寂    时间: 2009-04-19 10:03
标题: 回复 #4 efhilt 的帖子
嗯 动态规划，但是用递归的话经常很多结果都重复产生了，占用资源增加，计算效率降低。
作者: apzc2529    时间: 2009-04-19 13:51
刚算了一个Project Euler(76)上的题。也是使用的递归，速度确实有点慢。
代码：
'''
The number of the integer solutions of a_1*x_1+a_2*x_2+...+a_V*V=N
'''
try:
        import psyco
        psyco.full()
except ImportError:
        pass
def P(V,N):
        if N< =1 or V==2:
                return N/2+1
        elif V==1:
                return 1
        elif N<V:
                return P(N-1,N)+1
        else:
                return sum([P(V-1,N-V*x) for x in xrange(N/V+1)])
print P(99,100)




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2