Bone Collector

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 14134    Accepted Submission(s): 5585

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

³¹).

 

 

Sample Input

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

 

 

Sample Output

14

1 //下面的不对  2 #include 
        
          3 #include 
         
           4 using namespace std; 5 typedef struct Node 6 { 7     int w,value; 8 }Node; 9 Node bag[1010];10 int f[1010][1010];11 int main()12 {13     int i,j,k,t,T;14     cin>>T;15     while(T--)16     {17         int n,c;18         cin>>n>>c;19         memset(bag,0,sizeof(bag));20         memset(f,0,sizeof(f));21         for(i=1;i<=n;i++)22             cin>>bag[i].value;23         for(i=1;i<=n;i++)24             cin>>bag[i].w;25         f[1][c] = bag[1].value;26         for(i=2;i<=n;i++)27         {28             if(c>=bag[i].w)29             {30                 int temp = f[i-1][c-bag[i].w] + bag[i].value;31                 f[i][c] = max(temp,f[i-1][c]);32             }33             else 34                 f[i][c] = f[i-1][c];35         }36         cout<
          
           <
          
         
        

1 #include 
       
         2 #include 
        
          3 using namespace std; 4 int w[1010]; 5 int value[1010]; 6 int f[1010][1010]; 7 int main() 8 { 9     int i,j,k,t,T;10     cin>>T;11     while(T--)12     {13         int n,c;14         cin>>n>>c;15         memset(w,0,sizeof(w));16         memset(f,0,sizeof(f));17         memset(value,0,sizeof(value));18         for(i=1;i<=n;i++)19             cin>>value[i];20         for(i=1;i<=n;i++)21             cin>>w[i];22         for(i=1;i<=n;i++)23             for(j=0;j<=c;j++)24             if(j>=w[i])25             {26                 f[i][j] = max(f[i-1][j],f[i-1][j-w[i]] + value[i]);27             }28             else29                 f[i][j] = f[i-1][j];30                 /*31                 //原来没加这一条语句32                 133                 5 034                 2 4 1 5 135                 0 0 1 0 036                 答案应该是1237                 却输出6 38                 */ 39             cout<
         
          <
         
        
       

 

1 //此时g++提交ac，c++wa，因为第二十九行的符号  2 #include 
       
         3 #include 
        
          4 using namespace std; 5 int w[1010]; 6 int value[1010]; 7 int f[1010][1010]; 8 int main() 9 {10     int i,j,k,t,T;11     cin>>T;12     while(T--)13     {14         int n,c;15         cin>>n>>c;16         memset(w,0,sizeof(w));17         memset(f,0,sizeof(f));18         memset(value,0,sizeof(value));19         for(i=1;i<=n;i++)20             cin>>value[i];21         for(i=1;i<=n;i++)22             cin>>w[i];23         for(i=1;i<=n;i++)24             for(j=0;j<=c;j++)25             {26                 f[i][j] = f[i-1][j];27                 if(j>=w[i])28                 {29                     f[i][j] >?= f[i-1][j-w[i]] + value[i];30                 }31             }32             cout<
         
          <
         
        
       

 

1 //滚动数组优化空间和时间复杂度 ,时间上不太明显  2 #include 
       
         3 #include 
        
          4 using namespace std; 5 int w[1010]; 6 int value[1010]; 7 int f[1010]; 8 int main() 9 {10     int i,j,k,t,T;11     cin>>T;12     while(T--)13     {14         int n,c;15         cin>>n>>c;16         memset(w,0,sizeof(w));17         memset(f,0,sizeof(f));18         memset(value,0,sizeof(value));19         for(i=1;i<=n;i++)20             cin>>value[i];21         for(i=1;i<=n;i++)22             cin>>w[i];23         for(i=1;i<=n;i++)24             for(j=c;j>=w[i];j--)25             {26                 f[j] >?= f[j-w[i]] + value[i];27             }28             cout<
         
          <