多重背包的模型，但一开始直接将N个物品一个一个拆，拆成01背包竟然T了！！好吧OI过后多久没看过背包问题了，翻出背包九讲看下才发现还有二进制优化一说。。。。。。。。就是将n个物品拆成系数：1,2,4，8....*物品价值和空间的物品，在这题中只要乘上money[i]就行了，从二进制考虑发现，这样可以组成0~n中所有的数
#include <iostream>
#include <cstdio>
#include<string.h>
using namespace std;
int max(int a,int b)
{
if(a>b)return a;else return b;
}
int main()
{
int cash,n,t,dp[100009]={0},money[200]={0},mone;
while(scanf("%d",&cash)!=EOF)
{
memset(dp,0,sizeof(dp));
scanf("%d",&n);
dp[0]=1;
int cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&t,&mone);
int k=1;
while(t-k>=0)
{
money[++cnt]=k*mone;
t-=k;
k<<=1;
}
if (t>0)money[++cnt]=t*mone;
}
for(int i=1;i<=cnt;i++)
{
for(int j=cash;j>=money[i];j--)
if (dp[j-money[i]])dp[j]=1;
}
while(dp[cash]==0)
{
cash--;
}
printf("%d\n",cash);
}
return 0;
}