Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 21408    Accepted Submission(s): 8610
Problem 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
31).
 
Sample Input 
 
     
       1 5 10 1 2 3 4 5 5 4 3 2 1 
     
 
    
 
    
        
    
 
    
 
    
      Sample Output 
    
 
    
 
     
 
     
       14 
     
 
    
 
    
        
    
 
    
 
    
      Author 
    
 
    
      Teddy 
    
 
    
        
    
 
    
 
    
      Source 
    
 
    
 
    
 
    
        
    
 
    
 
    
      Recommend 
    
 
    
      lcy 
    
 
    
 
    
解题思路：本题为典型01背包问题，直接用01背包求解即可。（01背包相关内容点这里：）
 
    
         解释状态转移方程：dp[j]=dp[j]>(dp[j-wei[i]]+val[i])?dp[j]:(dp[j-wei[i]]+val[i]);
 
    
         原始方程：dp[i][j]=dp[i-1][j]>(dp[i-1][j-wei[i]]+val[i])?dp[i-1][j]:(dp[i-1][j-wei[i]]+val[i]);语意解析：对于第i件物品和背包剩余容量为j时的最佳值（骨头价值最大）=max{对于第i-1件物品和背包剩余容量为j时的最佳值（第i件不放入背包），对于第i-1件物品和背包剩余容量为（j-第i件物品的重量）时的最佳值+第i件物品的价值（第i件放入背包）}
 
    
        可以用滚动数组解答，原始方程可化为：dp[j]=dp[j]>(dp[j-wei[i]]+val[i])?dp[j]:(dp[j-wei[i]]+val[i]);当处理第i件物品时，dp[j]，dp[j-wei[i]]中存储的值就是dp[i-1][j]，dp[i-1][j-wei[i]]的值，所以在处理时(i=0;i<n;i++)&&(j=v;j>=0;j--)如是即可。
 
    
 
    
 
    
 
    
#include
     
       #include
      
        int main() {     int val[1002],wei[1002];  //骨头价值，骨头重量     int dp[1002];     int t,n,v;     int i,j;     scanf("%d",&t);     while(t--)     {         scanf("%d%d",&n,&v);         for(i=0;i
       
        =0;j--)                 if(j-wei[i]>=0)                     dp[j]=dp[j]>(dp[j-wei[i]]+val[i])?dp[j]:(dp[j-wei[i]]+val[i]);         printf("%d\n",dp[v]);     }     return 0; }