hdu 2191 多重背包

http://acm.hdu.edu.cn/showproblem.php?pid=2191

#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<iostream>
 #include<algorithm>
 using namespace std;


 struct ele
 {
     int price;
     int wight;
     int num;
 }p[120];
 int a[888];
 int b[888];
 int dp[888];


 int main()
 {
     int T;
     int V,N;
     int i,j,k;
     int cnt;
     int l;
     scanf("%d",&T);
     while(T--)
     {
         cnt=1;
         scanf("%d%d",&V,&N);
         for(i=1;i<=N;i++)
         {
             scanf("%d%d%d",&p[i].price,&p[i].wight,&p[i].num);
             l=1;
             while(p[i].num>=l)
             {
                 a[cnt]=p[i].price*l;
                 b[cnt++]=p[i].wight*l;
                 p[i].num-=l;
                 l<<=1;
             }
             if(p[i].num)
             {
                 a[cnt]=p[i].price*p[i].num;
                 b[cnt++]=p[i].wight*p[i].num;
             }
         }
         memset(dp,0,sizeof(dp));
         for(i=1;i<cnt;i++)
             for(k=V;k>=a[i];k--)
                     dp[k]=max(dp[k],dp[k-a[i]]+b[i]);
         printf("%d\n",dp[V]);
     }
     return 0;
 }

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

struct ele
{
    int price;
    int wight;
    int num;
}p[120];
int dp[120];

int main()
{
    int T;
    int V,N;
    int i,j,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&V,&N);
        for(i=1;i<=N;i++)
            scanf("%d%d%d",&p[i].price,&p[i].wight,&p[i].num);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=N;i++)
            for(j=1;j<=p[i].num;j++)
                for(k=V;k>=p[i].price;k--)
                    dp[k]=max(dp[k],dp[k-p[i].price]+p[i].wight);
        printf("%d\n",dp[V]);
    }
    return 0;
}