问题描述：
设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
编程任务：
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。
数据输入：
由文件input.txt 提供输入数据，文件的第一行中只有1 个整数给出n的值,第2 行起每行2 个数，分别是T[j]和Coins[j]。最后1 行是要找的钱数m。
结果输出:
程序运行结束时，将计算出的最少硬币数输出到文件output.txt中。问题无解时输出-1。
输入文件示例 输出文件示例
input.txt
3
1 3
2 3
5 3
18
output.txt
5
问题分析：
因为题目对每种面值的硬币数目有限制，所以不能使用贪心算法可能得不到正确的结果。此处可以采用动态规划或者深度优先搜索的方法。下面分别介绍两种方法。
1.深度优先搜索方法
对于给定的钱数m，和给定的货币种类n，第n种货币的选择有0,1,..,min{m/t[n]，coins[n]}。假设第n种货币数量选定了为k,那么剩下的钱数为m-k,剩下的货币种类为n-1，此时进行递归即可。
深度优先搜索方法的时间复杂度为coins[1]*coins[1]*..*coins[n]，但实际上可以再搜索过程中进行一些剪枝操作，实际上可以大大降低时间复杂度。
2.动态规划算法
设s[i][k]表示对于钱数k，选择前i种货币种类所需要的最少硬笔数，则s[i][k]=min{s[i-1][k-j*t[i]]+j},0=<j<=min{coins[i],k/t[i]}，
下面给出动态规划算法的c++源码
#include<iostream>
#include<fstream>
using namespace std;
#define INF 1<<30
int minCoin(int coins[],int t[],int n,int m)
{
int i=0;
int k=0;
int j=0;
int **s=(int **)malloc(sizeof(int *)*(n+1));
for(i=0;i<=n;i++)
{
s[i]=(int *)malloc(sizeof(int)*(m+1));
//二维数组元素s[i][j]的初始值为-1,表示对于钱数j,前i种硬币不能找零
memset(s[i],-1,sizeof(int)*(m+1));
}
for(i=0;i<=n;i++)
{
//对于钱数为0，s[i][0]=0;
s[i][0]=0;
}
int min=INF;
for(i=1;i<=n;i++)
{
for(k=i;k<=m;k++)
{
for(j=0;j<=coins[i-1]&&j<=k/t[i-1];j++)
{
//如果s[i-1][k-j*t[i-1]]<0表示如果第i种货币使用j个，那么剩下的i-1种货币用来找零钱数k-j*t[i-1]不成功
if(s[i-1][k-j*t[i-1]]+j<min&&s[i-1][k-j*t[i-1]]>=0)
min=s[i-1][k-j*t[i-1]]+j;
}
if(min!=INF)
s[i][k]=min;
min=INF;
}
}
return s[n][m];
}
int main()
{
ifstream in("input.txt");
int n,m;
in>>n;
int *coins=new int[n];
int *t=new int[n];
for(int i=0;i<n;i++)
{
in>>t[i]>>coins[i];
}
in>>m;
int res=minCoin(coins,t,n,m);
cout<<res<<endl;
return 0;
}