原题链接http://acm.hdu.edu.cn/showproblem.php?pid=5410

因为他每买一件物品就会得到Ai颗糖，每买一种物品就会得到Bi颗糖。有两个价值。。所以我们应该先用一次01背包把两个价值统一起来。。。因为01背包中每种物品只能取一次。。。。然后我们用多重背包来决定应该多买哪种物品得到的糖果最多。。。。==

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn=1010;__int64 dp[2010];int w[maxn],a[maxn],b[maxn];int main(){    int t,n,W;    scanf("%d",&t);    while(t--)    {        memset(dp,0,sizeof(dp));        int i,j;        scanf("%d%d",&W,&n);        for(i=1;i<=n;i++)        scanf("%d %d %d",&w[i],&a[i],&b[i]);        for(i=1;i<=n;i++)        {            for(j=W;j>=w[i];j--)            {                dp[j]=max(dp[j],dp[j-w[i]]+a[i]+b[i]);            }        }         for(i=1;i<=n;i++)        {            for(j=0;j<=W;j++)            {            if(j>=w[i])            dp[j]=max(dp[j],dp[j-w[i]]+a[i]);           }        }        printf("%I64d\n",dp[W]);    }    return 0;}