首页 > 代码库 > hdu 2602

hdu 2602

题意:n个物品,V容量,每个物品的价值体积给出,问最大价值

思路:01背包

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int t;
 6     int i,j;
 7     int n,v;
 8     int jiazhi[1003],tiji[1003],dp[1003];
 9     scanf("%d",&t);
10     while(t--)
11     {
12         memset(dp,0,sizeof(dp));
13         scanf("%d%d",&n,&v);
14         for(i=1;i<=n;i++)
15             scanf("%d",&jiazhi[i]);
16         for(i=1;i<=n;i++)
17             scanf("%d",&tiji[i]);
18         for(i=1;i<=n;i++)
19         {
20             for(j=v;j>=tiji[i];j--)
21             {
22                 dp[j]=max(dp[j],dp[j-tiji[i]]+jiazhi[i]);
23             }
24         }
25         printf("%d\n",dp[v]);
26     }
27     return 0;
28 }

 

hdu 2602