算法题——钱币组合问题

千年沉寂

钱币组合问题

    问题描述：设有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 种不同钱币，编程计算某个给定面值能有多少种不同的产生方法。

千年沉寂

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

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

递归，还是递归。

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

1. 
   
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
    
15. 
    

复制代码

千年沉寂

嗯 动态规划，但是用递归的话经常很多结果都重复产生了，占用资源增加，计算效率降低。

apzc2529

刚算了一个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)