hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活(多重背包）

tmp<<=1粗心写成tmp>>=1

居然RE?!没想明白怎么是RE。。。。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int v[110],w[110],c[110],p[1010],ww[1010];
int dp[110];

int main()
{
    int T,sum,ans,tmp,r,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&sum,&n);
        for(int j=0;j<n;j++)
            scanf("%d%d%d",&v[j],&w[j],&c[j]);
        memset(dp,0,sizeof(dp));
        for(int j=0;j<n;j++)
        {
            if(v[j]*c[j]>=sum)
            {
                for(int k=v[j];k<=sum;k++)
                    dp[k]=max(dp[k],dp[k-v[j]]+w[j]);
            }
            else
            {
                tmp=1;r=0;
                while(c[j]>=tmp)
                {
                    ww[r]=tmp*w[j];
                    p[r++]=tmp*v[j];
                    c[j]-=tmp;
                    tmp<<=1;
                }
                if(c[j])
                {
                    ww[r]=w[j]*c[j];
                    p[r++]=v[j]*c[j];
                }
                for(int k=0;k<r;k++)
                {
                    for(int u=sum;u>=p[k];u--)
                        dp[u]=max(dp[u],dp[u-p[k]]+ww[k]);
                }
            }
        }
        ans=-1;
        for(int j=0;j<=sum;j++)
        {
            if(dp[j]>ans)
                ans=dp[j];
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活(多重背包）

原文：http://blog.csdn.net/u012841845/article/details/18601091