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 ?
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.
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
View Code
1 //下面的不对 2 #include <iostream> 3 #include <cstring> 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<<f[n][c]<<endl; 37 } 38 return 0; 39 } 40
1 #include <iostream> 2 #include <cstring> 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 else 29 f[i][j] = f[i-1][j]; 30 /* 31 //原来没加这一条语句 32 1 33 5 0 34 2 4 1 5 1 35 0 0 1 0 0 36 答案应该是12 37 却输出6 38 */ 39 cout<<f[n][c]<<endl; 40 } 41 return 0; 42 } 43
1 //此时g++提交ac，c++wa，因为第二十九行的符号 2 #include <iostream> 3 #include <cstring> 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<<f[n][c]<<endl; 33 } 34 return 0; 35 } 36
1 //滚动数组优化空间和时间复杂度 ,时间上不太明显 2 #include <iostream> 3 #include <cstring> 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<<f[c]<<endl; 29 } 30 return 0; 31 } 32 //注意一条：不可用结构体存储重量和价值
