**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 **Sample Output** 5 此问题相当于将n种物品装入背包，每种物品有数量限制，求装满背包所需的最少物品数。此题可视多重背包问题中每个物品的价值都为1，然后求装满后总价值的最小值。背包问题一般都是求最大值，而此题需要求最小值，这需要在设置dp数组的初始值设为正无穷，但不能设为整型的最大值，否则加上一个值后会溢出变成负数，产生错误的结果。 ```cpp #include <iostream> #include <cstdio> #include <string.h> #include <memory.h> #include <queue> #include <stack> #include <cmath> using namespace std; int main() { int dp[20002],t[10],coins[10],n,m; cin>>n; for(int i=0;i<n;++i) cin>>t[i]>>coins[i]; cin>>m; dp[0]=0; for(int i=1;i<=m;++i) dp[i]=0x7ffffff; for(int i=0;i<n;++i) for(int j=0;j<coins[i];++j) for(int k=m;k>=t[i];--k) dp[k]=min(dp[k],dp[k-t[i]]+1); if(dp[m]>=0x7ffffff) cout<<-1; else cout<<dp[m]; return 0; } ```