题目大意
给定一个容量为M的背包以及n种物品，每种物品有一个体积和数量，要求你用这些物品尽量的装满背包
题解
就是多重背包~~~~用二进制优化了一下，就是把每种物品的数量cnt拆成由几个数组成，1，2，4，~~~cnt-2^K+1,k满足cnt-2^K+1>0的最大整数，体积和价值乘上相应的数就是相应物品的价值和体积，这样用这些物品能够表示1~~cnt所有的情况~~~这就转化成01背包了~~~
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define MAXN 100005
int dp[MAXN];
int value[],cnt[];
int cash,n;
void CompletePack(int c,int w)
{
for(int i=c; i<=cash; i++)
dp[i]=max(dp[i],dp[i-c]+w);
}
void ZeroOnePack(int c,int w)
{
for(int i=cash; i>=c; i--)
dp[i]=max(dp[i],dp[i-c]+w);
}
void MultiplePack(int c,int w,int m)
{
if(c*m>=cash)
{
CompletePack(c,w);
return;
}
int k=;
while(k<m)
{
ZeroOnePack(k*c,k*w);
m-=k;
k*=;
}
if(m>) ZeroOnePack(c*m,w*m);
}
int main()
{ while(scanf("%d",&cash)!=EOF)
{
scanf("%d",&n);
for(int i=; i<=n; i++) scanf("%d%d",&cnt[i],&value[i]);
memset(dp,,sizeof(dp));
for(int i=; i<=n; i++)
MultiplePack(value[i],value[i],cnt[i]);
printf("%d\n",dp[cash]);
}
return ;
}