递归的算法设计
问题：有n种面额的纸币（x1，x2，...，xn），求支付y元所需的最少张数请问具体的思路应该怎么写？ 这个不是背包问题么？ 百度即可 本帖最后由 指头比思想慢 于 2020-11-6 13:51 编辑
动态规划问题，然后再用一个数据结构保存规划中间节点的信息来避免重复计算
可以参考我这样写的
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
# 如果待支付量存在于面额序列中则直接返回该面额，因为1为最小数量支付方式，但是要包装为list
if x in self.chioes:
self.pay_dict =
else:
# 如果待支付量既不存在最优解字典中，也不在面额序列中，则需要退一步求解上一个支付量
#上一个支付量即为本次支付量遍历减所有面额
for i in self.chioes:
if x-i < self.chioes: # 如果所减得到的支付量小于最小面额，则不存在解，跳出循环
break
if self.pay(x-i): # 如果所减面额存在解
res = + self.pay(x-i) # 减掉的面额 加上 前一个支付量的解，即为本支付量解
if x not in self.pay_dict:
self.pay_dict = res
if len(res) < len(self.pay_dict): # 本支付量虽然有解，但不一定是最优解，需要和最优解字典中的解比较
self.pay_dict = res
return self.pay_dict.get(x, None)
mypay = MyPay(a)
mypay.pay(14) 本帖最后由 jackz007 于 2020-11-6 13:56 编辑
取得面额数量，根据面额数量取得各个面额值保存到数组，按从大到小的顺序，对面额值数组重新排序，输入目标金额，循环，按面额由大到小的顺序拼凑目标金额，直到最终完成。
下面是我按照上述思想编写的代码及编译、运行实况，谨供楼主参考
#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 > g ; j --) {
t = g ;
g = g ;
g = t ;
}
}
}
main(void)
{
float g , r , t ;
int h , f , k , m , n ;
printf("请输入面额数量：") ;
scanf("%d" , & m) ;
printf("请输入面额数值：") ;
for(k = 0 ; k < m ; k ++) scanf("%f" , & g) ;
sort(g , m) ;
printf("请输入目标金额：") ;
scanf("%f" , & t) ;
for(r = 0.0 , f = 0 , n = 0 , k = 0 ; k < m && r < t ; k ++) {
h = 0 ;
while(r + g <= t) {
r += g ;
h ++ ;
}
if(r == t) {
n = k + 1 ;
f ++ ;
break ;
}
}
if(f) {
printf("\n目标 %.2f 元的最佳组合方案为：\n" , t) ;
for(k = 0 ; k < n ; k ++) if(h) printf("%6.2f x %d\n" , g , h) ;
} 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>
qqq
本帖最后由 蹒跚学步小咸鱼 于 2020-11-6 13:47 编辑
页:
[1]