递归的算法设计

白牡丹秀色可餐

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

耶稣

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

指头比思想慢

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

import numpy as np
a = np.random.randint(1, 20, 6)
a = set(a)
a = list(a)
print(a)


class MyPay():
    def __init__(self, chioes):
        self.pay_dict = {} # 保存各种支付量的最优解字典
        self.chioes = chioes # 已排序的面额序列
        
    def pay(self, x):
        # 如果待支付量已经存在于最优解字典中则直接返回
        if x in self.pay_dict:
            return self.pay_dict[x]
        
        # 如果待支付量存在于面额序列中则直接返回该面额，因为1为最小数量支付方式，但是要包装为list
        if x in self.chioes:
            self.pay_dict[x] = [x]
        else:
            # 如果待支付量既不存在最优解字典中，也不在面额序列中，则需要退一步求解上一个支付量
            #上一个支付量即为本次支付量遍历减所有面额
            for i in self.chioes:
                if x-i < self.chioes[0]: # 如果所减得到的支付量小于最小面额，则不存在解，跳出循环
                    break
                if self.pay(x-i): # 如果所减面额存在解
                    res = [i]+ self.pay(x-i) # 减掉的面额 加上 前一个支付量的解，即为本支付量解
                    if x not in self.pay_dict:
                        self.pay_dict[x] = res
                    if len(res) < len(self.pay_dict[x]): # 本支付量虽然有解，但不一定是最优解，需要和最优解字典中的解比较
                        self.pay_dict[x] = res
        return self.pay_dict.get(x, None)
    
mypay = MyPay(a)
mypay.pay(14)

jackz007

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

#include <stdio.h>

void sort(float g[] , const int m)
{
        float t                         ;
        int i , j                       ;
        for(i = 1 ; i < m ; i ++) {
                for(j = i ; j && g[j] > g[j - 1] ; j --) {
                        t = g[j]        ;
                        g[j] = g[j - 1] ;
                        g[j - 1] = t    ;
                }
        }
}

main(void)
{
        float g[100] , r , t                                                           ;
        int h[100] , f , k , m , n                                                     ;
        printf("请输入面额数量：")                                                     ;
        scanf("%d" , & m)                                                              ;
        printf("请输入面额数值：")                                                     ;
        for(k = 0 ; k < m ; k ++) scanf("%f" , & g[k])                                 ;
        sort(g , m)                                                                    ;
        printf("请输入目标金额：")                                                     ;
        scanf("%f" , & t)                                                              ;
        for(r = 0.0 , f = 0 , n = 0 , k = 0 ; k < m && r < t ; k ++) {
                h[k] = 0                                                               ;
                while(r + g[k] <= t) {
                        r += g[k]                                                      ;
                        h[k] ++                                                        ;
                }
                if(r == t) {
                        n = k + 1                                                      ;
                        f ++                                                           ;
                        break                                                          ;
                }
        }
        if(f) {
                printf("\n目标 %.2f 元的最佳组合方案为：\n" , t)                        ;
                for(k = 0 ; k < n ; k ++) if(h[k]) printf("%6.2f x %d\n" , g[k] , h[k]) ;
        } else printf("抱歉：问题无解\n")                                               ;
        printf("\n")                                                                    ;
}

编译、运行效果：

D:\0002.Exercise\C>g++ -o x x.c

D:\0002.Exercise\C>x
请输入面额数量：6
请输入面额数值：1 5 10 20 50 100
请输入目标金额：999

目标 999.00 元的最佳组合方案为：
100.00 x 9
 50.00 x 1
 20.00 x 2
  5.00 x 1
  1.00 x 4

D:\0002.Exercise\C>

蹒跚学步小咸鱼

qq