http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
题目大意：有n[i]个面值为d[i]的硬币，要用这些硬币拼出价值为cash的钱来。如果拼不出，就拼出一个小于cash的最大的面值。求这个面值。
思路：
依次考虑这n个面值，用sum[i]表示，当只用前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");
}
}