问题标题: 酷町堂:1216 硬币找零 求思路

0
0
已解决
薛乘志
薛乘志
初级启示者
初级启示者

在现实生活中,我们经常遇到硬币找零的问题,例如,在发工资时,财务人员就需要计算最少的找零硬币数,以便他们能从银行拿回最少的硬币数,并保证能用这些硬币发工资。
我们应该注意到,人民币的硬币**是 100,50,20,10,5,2,1,0.5,0.2,0.1,0.05,
0.02,0.01 元,采用这些硬币我们可以对任何一个工资数用贪心算法求出其最少硬币数。
但不幸的是: 我们可能没有这样一种好的硬币**, 因此用贪心算法不能求出最少的硬币数,甚至有些金钱总数还不能用这些硬币找零。例如,如果硬币**是 40,30,25 元,那么 37元就不能用这些硬币找零;95 元的最少找零硬币数是 3。又如,硬币**是 10,7,5,1元,那么 12 元用贪心法得到的硬币数为 3,而最少硬币数是 2。
你的任务就是:对于任意的硬币**和一个金钱数,请你编程求出最少的找零硬币数;
如果不能用这些硬币找零,请给出一种找零方法,使剩下的钱最少。

输入描述 Input Description

输入数据:
第 1 行,为 N 和 T,其中 1≤N≤50 为硬币**中不同硬币数;1≤T≤100000 为需要用硬币找零的总数。
第 2 行为 N 个数值不大于 100000的正整数,它们是硬币**中各硬币的面值。
当n,t同时为0时结束。

输出描述 Output Description

输出数据:
如 T 能被硬币**中的硬币找零,请输出最少的找零硬币数。
如 T 不能被硬币**中的硬币找零,请输出剩下钱数最少的找零方案中的最少硬币数。

 

思路,不要完整代码!!!

薛乘志在2023-01-21 08:44:26追加了内容

1

薛乘志在2023-01-21 08:45:35追加了内容

1

薛乘志在2023-01-21 08:47:18追加了内容

33333

薛乘志在2023-01-21 09:01:09追加了内容

你好

薛乘志在2023-01-21 09:03:22追加了内容

你好

薛乘志在2023-01-21 09:05:52追加了内容

0
已采纳
汪宇航
汪宇航
新手启示者
新手启示者

想一想,因为这道题可转变成01背包

汪宇航在2021-09-05 14:11:38追加了内容

鸭,把多重背包也截进来了

0
0
汪宇航
汪宇航
新手启示者
新手启示者

搞错了,是完全背包,动态规划

0
汪宇航
汪宇航
新手启示者
新手启示者

这上面是例题的转化,这道题怎么转化**你了

我要回答