最少硬币问题
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
1 3
2 3
5 3
18
Output
5
此题解法：
此题我们需要把每一种硬币面值按照其数量一一摆开，对于每一种硬币，for(i)遍历从0到n，
再对于该硬币的数量，for(j)遍历从1到 该硬币真实数量coin[i]，
再对于当前所需找回面额k，for(k)遍历从m到 该硬币面额T[i]，
如果当前所需找回面额k 大于 该硬币面额T[i]，则判断
若将该硬币替换进结果组合中，所需硬币数dp[k]变少，则替换，否则下一步，k--，
直到 当所需找回面额k 小于 该硬币面额T[i]时，跳回上层for循环，改变硬币数量j 这个条件，继续计算 所需硬币数dp[k]，
当该硬币数目j 达到最大值，则改变 硬币种类i 这个条件，为dp推导增加新的硬币面值，
直到 所有硬币钟类 的 每一个硬币 对于 每一个所需找回面额 都遍历完成，
则判断题目要求的 找回m元所需最小硬币数的 dp[m] 是否计算出结果，
若算出结果，则输出dp[m]，若没算出，则输出 -1 。
#include <iostream>
#include <cstdio>
#include <cstring>///包含memset()
#define MAX 0x3f3f3f3f ///定义最大值MAX
using namespace std;
///参考1 https://www.cnblogs.com/onetrainee/p/11672907.html
///参考2 https://blog.csdn.net/q623702748/article/details/51297949
///参考3 https://blog.csdn.net/u013326239/article/details/51540956
/***
设计一个用最少硬币找钱m的方法
dp[目标面额]=达到当前面额需要最少的硬币数量
dp[目标面额] = min(dp[目标面额-当前面额]+1，dp[目标面额])
dp[目标面额-当前面额]+1 相当于替换掉 当前面额的硬币
将 每一种硬币 的 每一个硬币 一个一个的加入判断，
若增加该硬币会使 所需硬币数量 变少，则更新 dp[当前面额] (当前面额所需硬币)
***/
int min(int, int);
int T[15];///T[i]表示 第i种硬币的面值
int coins[15];///coins[i]表示第i种硬币的个数
long long int dp[20011];///dp[目标面额] 表示达到当前面额需要最少的硬币数量
int main()
{
int n, m;///有n种硬币，需要找回的目标面额是m
memset(dp, MAX, sizeof(dp));
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &T[i]);
scanf("%d", &coins[i]);
}
scanf("%d", &m);
dp[0] = 0;///边界条件，当目标面额是0时，需要0个硬币
for(int i = 0; i < n; i++)
{///i是第i种硬币，遍历每一种硬币
for(int j = 1; j <= coins[i]; j++)
{///j是硬币个数，每一种硬币有coins[i]个，对第i种硬币的每一个硬币都遍历
for(int k = m; k >= T[i]; k--)
{///k是当前面额，当当前需要找回的面额 大于等于 第i种硬币的面值
///判断已保存的dp[当前面额]的值 和 dp[替换掉当前面额]的值 的大小
dp[k] = min(dp[k], dp[k - T[i]] + 1);
}
}
}
printf("%lld\n", dp[m] < MAX ? dp[m] : -1);
///判断dp[m]是否小于设定的最大值，若小于，则输出dp[m]，若不小于则问题无解，输出-1
return 0;
}
int min(int x, int y)
{
if(x < y)
return x;
else
return y;
}
参考：
https://www.cnblogs.com/onetrainee/p/11672907.html | 
转播
