递归的算法设计

白牡丹秀色可餐

问题：有n种面额的纸币（x1，x2，...，xn），求支付y元所需的最少张数
请问具体的思路应该怎么写？

耶稣

这个不是背包问题么？ 百度即可

指头比思想慢

动态规划问题，然后再用一个数据结构保存规划中间节点的信息来避免重复计算
可以参考我这样写的

1. import numpy as np
   
2. a = np.random.randint(1, 20, 6)
   
3. a = set(a)
   
4. a = list(a)
   
5. print(a)
   
6. 
   
7. 
   
8. class MyPay():
   
9.     def __init__(self, chioes):
   
10.         self.pay_dict = {} # 保存各种支付量的最优解字典
    
11.         self.chioes = chioes # 已排序的面额序列
    
12.         
    
13.     def pay(self, x):
    
14.         # 如果待支付量已经存在于最优解字典中则直接返回
    
15.         if x in self.pay_dict:
    
16.             return self.pay_dict[x]
    
17.         
    
18.         # 如果待支付量存在于面额序列中则直接返回该面额，因为1为最小数量支付方式，但是要包装为list
    
19.         if x in self.chioes:
    
20.             self.pay_dict[x] = [x]
    
21.         else:
    
22.             # 如果待支付量既不存在最优解字典中，也不在面额序列中，则需要退一步求解上一个支付量
    
23.             #上一个支付量即为本次支付量遍历减所有面额
    
24.             for i in self.chioes:
    
25.                 if x-i < self.chioes[0]: # 如果所减得到的支付量小于最小面额，则不存在解，跳出循环
    
26.                     break
    
27.                 if self.pay(x-i): # 如果所减面额存在解
    
28.                     res = [i]+ self.pay(x-i) # 减掉的面额 加上 前一个支付量的解，即为本支付量解
    
29.                     if x not in self.pay_dict:
    
30.                         self.pay_dict[x] = res
    
31.                     if len(res) < len(self.pay_dict[x]): # 本支付量虽然有解，但不一定是最优解，需要和最优解字典中的解比较
    
32.                         self.pay_dict[x] = res
    
33.         return self.pay_dict.get(x, None)
    
34.    
    
35. mypay = MyPay(a)
    
36. mypay.pay(14)

复制代码

jackz007

        取得面额数量，根据面额数量取得各个面额值保存到数组，按从大到小的顺序，对面额值数组重新排序，输入目标金额，循环，按面额由大到小的顺序拼凑目标金额，直到最终完成。
        下面是我按照上述思想编写的代码及编译、运行实况，谨供楼主参考

1. #include <stdio.h>
   
2. 
   
3. void sort(float g[] , const int m)
   
4. {
   
5.         float t                         ;
   
6.         int i , j                       ;
   
7.         for(i = 1 ; i < m ; i ++) {
   
8.                 for(j = i ; j && g[j] > g[j - 1] ; j --) {
   
9.                         t = g[j]        ;
   
10.                         g[j] = g[j - 1] ;
    
11.                         g[j - 1] = t    ;
    
12.                 }
    
13.         }
    
14. }
    
15. 
    
16. main(void)
    
17. {
    
18.         float g[100] , r , t                                                           ;
    
19.         int h[100] , f , k , m , n                                                     ;
    
20.         printf("请输入面额数量：")                                                     ;
    
21.         scanf("%d" , & m)                                                              ;
    
22.         printf("请输入面额数值：")                                                     ;
    
23.         for(k = 0 ; k < m ; k ++) scanf("%f" , & g[k])                                 ;
    
24.         sort(g , m)                                                                    ;
    
25.         printf("请输入目标金额：")                                                     ;
    
26.         scanf("%f" , & t)                                                              ;
    
27.         for(r = 0.0 , f = 0 , n = 0 , k = 0 ; k < m && r < t ; k ++) {
    
28.                 h[k] = 0                                                               ;
    
29.                 while(r + g[k] <= t) {
    
30.                         r += g[k]                                                      ;
    
31.                         h[k] ++                                                        ;
    
32.                 }
    
33.                 if(r == t) {
    
34.                         n = k + 1                                                      ;
    
35.                         f ++                                                           ;
    
36.                         break                                                          ;
    
37.                 }
    
38.         }
    
39.         if(f) {
    
40.                 printf("\n目标 %.2f 元的最佳组合方案为：\n" , t)                        ;
    
41.                 for(k = 0 ; k < n ; k ++) if(h[k]) printf("%6.2f x %d\n" , g[k] , h[k]) ;
    
42.         } else printf("抱歉：问题无解\n")                                               ;
    
43.         printf("\n")                                                                    ;
    
44. }

复制代码

编译、运行效果：

1. D:\0002.Exercise\C>g++ -o x x.c
   
2. 
   
3. D:\0002.Exercise\C>x
   
4. 请输入面额数量：6
   
5. 请输入面额数值：1 5 10 20 50 100
   
6. 请输入目标金额：999
   
7. 
   
8. 目标 999.00 元的最佳组合方案为：
   
9. 100.00 x 9
   
10. 50.00 x 1
    
11. 20.00 x 2
    
12.   5.00 x 1
    
13.   1.00 x 4
    
14. 
    
15. D:\0002.Exercise\C>

复制代码

蹒跚学步小咸鱼

qq