Bone Collector

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 46744 Accepted Submission(s): 19463

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

15 101 2 3 4 55 4 3 2 1

Sample Output

Author

Teddy

Source

Recommend

lcy | We have carefully selected several similar problems for you:

第一类背包 for(i=1;i<=n;i++）

for(j=V;j>v[i];j--)

d[j]=max(d[j],d[j-v[i]]+jg[i])

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;struct bb{ long long v; long long jz;}a[1005];long long max(long long n,long long m){ if(n>=m)return n; else return m;}int main(){ long long n,m,vv,sum[1005]; cin>>n; while(n--) { cin>>m>>vv; memset(sum, 0, sizeof(sum)); for(int i=0;i
               
                >a[i].jz; } for(int i=0;i
                
                 >a[i].v; } for(int i=0;i
                 
                  =a[i].v;j--) { sum[j]=max(sum[j],sum[j-a[i].v]+a[i].jz); } } cout<
                  
                   <

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

你可能感兴趣的文章