http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
題目大意：有n[i]個面值為d[i]的硬幣，要用這些硬幣拼出價值為cash的錢來。如果拼不出，就拼出一個小于cash的最大的面值。求這個面值。
思路：
依次考慮這n個面值，用sum[i]表示，當(dāng)只用前i中面值時，是否可以拼出價值為i的錢。num[j]表示拼出價值為i的錢時，此時第i種面值用了多少個。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 100010
int m[12],d[12];
int num[maxn];
bool sum[maxn];
int main()
{
int cash,n;
while(scanf("%d%d",&cash,&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d%d",&m[i],&d[i]);
}
memset(sum,false,sizeof(sum));
sum[0]=1;
for(int i=0;i<n;i++)
{
memset(num,0,sizeof(num));
for(int j=d[i];j<=cash;j++)
{
if(!sum[j] && sum[j-d[i]] && num[j-d[i]]<m[i])
{
sum[j]=1;
num[j]=num[j-d[i]]+1;
}
}
}
bool flag=1;
for(int i=cash;i>=0;i--)
if(sum[i])
{
printf("%d\n",i);
flag=0;
break;
}
if(flag) printf("0\n");
}
}