HDOJ -- 2602 Bone Collector

 Bone Collector Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …  The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ? 

Input

The first line contain a integer T , the number of cases.  Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2  ³¹).

Sample Input

1 5 10 1 2 3 4 5 5 4 3 2 1

Sample Output

14

---

01背包基础入门题，对于01背包问题，一个显著的特点是：每种物品装入背包的数量要么是0要么是1。如果用V[i]表示第i件物品所占用的背包的体积，W[i]表示第i件物品的价值，用二维数组dp[i][j]来表示前i件物品恰好放入体积为j的背包中所获得的最大价值，那么： 1、当i不放入背包时,那么背包里就只有前i-1个物品，此时dp[i][j]=dp[i-1][j]； 2、当i放入背包中，那么未放入之前（即前i-1个物品）的体积为j-V[i],价值为dp[i-1][j-V[i]],此时dp[i][j]=dp[i-1][j-V[i]]+W[i]； 显然要取其中的最大者，于是动态方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+W[i]) 对于这道题，用一维数组也可以解决。用dp[i]表示背包体积为i时，所装的最大价值，然后逐个物品判断就行了，不过还是感觉二维的容易理解。 一位数组代码： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main(){ int t,n,v; int dp[1010],V[1010],w[1010]; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&v); for(int i=0;i<n;i++) scanf("%d",&w[i]); for(int i=0;i<n;i++) scanf("%d",&V[i]); memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) for(int j=v;j>=V[i];j--)//确保背包剩余体积大于即将要放入的物品的体积 dp[j]=max(dp[j],dp[j-V[i]]+w[i]); printf("%d\n",dp[v]); } return 0; } 二维数组代码： #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[1002][1002];//要定义在main函数外，否则爆内存！！ int main(){ int i,j,t,n,v; int W[1002],V[1002]; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&v); for(i=0;i<n;i++) scanf("%d",&W[i]); for(i=0;i<n;i++) scanf("%d",&V[i]); memset(dp,0,sizeof(dp)); for(i=0;i<V[0];i++) dp[0][i]=0; //当背包体积小于第一个物品体积时，价值为0 for(i=V[0];i<=v;i++) dp[0][i]=W[0];//反之为第一个物品的价值 for(i=1;i<n;i++){//从1开始判断 for(j=0;j<V[i];j++) dp[i][j]=dp[i-1][j];//小于物品i的体积时，i物品无法放入 for(j=V[i];j<=v;j++) dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+W[i]);//反之取最大者 } printf("%d\n",dp[n-1][v]); } return 0; }