POJ 1276 多重背包

模版题，贴个代码

#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <vector>#include <stack>#include <map>#include <iomanip>#define PI acos(-1.0)#define Max 100005#define inf 1<<28#define LL(x) (x<<1)#define RR(x)(x<<1|1)using namespace std;int c[Max],num[Max];int m;int dp[Max];void zero(int v)//0-1背包{    for(int i=m;i>=v;i--)    dp[i]=max(dp[i],dp[i-v]+v);//此题v=w}void com(int v)//完全背包{    for(int i=v;i<=m;i++)    dp[i]=max(dp[i],dp[i-v]+v);}void mu(int v,int w,int n)//多重背包{    if(v*n>=m)    {        com(v);        return ;    }    int k=1;    while(k<n)    {        zero(k*v);        n-=k;        k*=2;    }    zero(n*v);}int main(){    int i,j,k,l,n;    while(scanf("%d",&m)!=EOF)    {        scanf("%d",&n);        for(i=1;i<=n;i++)        scanf("%d%d",&num[i],&c[i]);        memset(dp,0,sizeof(dp));        for(i=1;i<=n;i++)        mu(c[i],c[i],num[i]);        cout<<dp[m]<<endl;    }    return 0;}