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
Sample Output
Hint
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 //
3
4 #include "pch.h"
5 #include <iostream>
6 #include <algorithm>
7 #define INF 0x3f3f3f3f
8 using namespace std;
9
10 int main() {
11
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 < n; i++) {
17 cin >> T[i] >> Coin[i];
18 }
19
20 cin >> des;
21 dp[0] = 0;
22
23 // 算法注意边界是否带等号
24 for (int i = 0; i < n; 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);
28
29 cout << (dp[des]<INF?dp[des]:-1) << endl;
30 }
31
[动态规划]最少硬币问题
原文：https://www.cnblogs.com/onetrainee/p/11672907.html
