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 231).
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 //注意一条：不可用结构体存储重量和价值