最少硬币问题,最少硬币问题 动态规划

将乐信息网 http://www.jianglexinxi.cn 2020-11-22 08:10 出处:网络
最少硬币问题,最少硬币问题 动态规划,[动态规划]最少硬币问题 最少硬币问题

最少硬币问题,最少硬币问题 动态规划,[动态规划]最少硬币问题

最少硬币问题

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/3016/pid/1725

Time Limit: 1000 ms Memory Limit: 65536 KiB   Problem Description 设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意钱数0≤m≤20001,设计一个用最少硬币找钱m的方法。
对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,计算找钱m的最少硬币数。 Input 输入数据第一行中只有1个整数给出n的值,第2行起每行2个数,分别是T[j]和Coins[j]。最后1行是要找的钱数m。 Output 输出数据只有一个整数,表示计算出的最少硬币数。问题无解时输出-1。 Sample Input
3
18
Sample Output
5
  Source

算法思路:

这题采用"动态规划"算法,将大问题转换为小问题,且一步步记录上一步的结果。 我们依旧使用一维数组来存储计算结果,可以参考之前的一个"背包问题"的算法解读:https://www.cnblogs.com/onetrainee/p/11672203.html

与"背包问题"的对比与分析:

“背包”中给出了"损失"与"收益",但其都是对于单个物品,求最大收益;“硬币”中给出的是"收益"、"个数"与"最终收益",求最小组合。 可以看出,如果对于"硬币问题",要采用动态规划的话,依照"一步步走的原则",至少要进行拆分,比如 5 个 2,要拆分成 5 、5,先计算第一个5,之后再计算第二个5。

算法设计:

依旧采用一维数组 "dp[目标面额]=最小需求个数" 来存储最终结果。 我们将所有硬币依次拆分成单个,dp[目标面额] = min(dp[目标面额-当前面额]+1,dp[目标面额]),前一个是将该面额放入该组合中,后一个是不采用当前面额,选取数值最小的。

算法注意事项:

前两层循环是将面额拆分,注意边界是否带等号。 dp[k]数组初始化时,除k=0外所有数值设置为无穷大,因为当需求为0时,其组合数本来就为0种,如果这个也设置为无穷大,则无法计算了。

源代码:

 

 1 // 算法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
 2 //
 4 #include "pch.h"
 5 #include iostream 
 6 #include algorithm 
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
10 int main() {
12 int des, n, T[20001], Coin[20001]; 
13 long long int dp[20001];
14 memset(dp, INF, sizeof(dp));
15 cin n;
16 for (int i = 0; i i++) {
17 cin T[i] Coin[i];
20 cin des;
21 dp[0] = 0;
23 // 算法注意边界是否带等号
24 for (int i = 0; i i++)
25 for (int j = 1; j = Coin[i]; j++)
26 for (int k = des; k = T[i]; k--)
27 dp[k] = min(dp[k], dp[k - T[i]] + 1); 
29 cout (dp[des] INF?dp[des]:-1) endl;
31 

 

本文标题:最少硬币问题,最少硬币问题 动态规划
http://www.jianglexinxi.cn/yanergaozhi/552904.html

0

精彩评论

暂无评论...
验证码 换一张
取 消