本文共 1897 字，大约阅读时间需要 6 分钟。

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 31). Sample Input 1 5 10 1 2 3 4 5 5 4 3 2 1 Sample Output 14

大致思路：

标准的01背包，创建一个二维数组dp[i][j]，i代表第i件物品，j代表剩余的背包容量。

但不知道为什么用滚动数组做就是WA。先记录一下。

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int dp[1000][1000];int main(){    int T;    cin>>T;    while(T--)    {        int N,V,value[1001],volume[1001];        cin>>N>>V;        for(int i=1;i<=N;++i)            cin>>value[i];        for(int i=1;i<=N;++i)            cin>>volume[i];        for(int i=1;i<=V;++i){            if(volume[1]<=i)                dp[1][i]=value[1];            else                dp[1][i]=0;        }        for(int i=2;i<=N;++i){            for(int j=V;j>=0;--j){                if(j>=volume[i])//状态转移方程                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]);                else                    dp[i][j]=dp[i-1][j];            }        }        cout<
       
        <
       
      
     
    
   

转载地址：http://lbobi.baihongyu.com/