HDOJ2602 Bone Collector

Bone Collector

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

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 ?
HDOJ-2602 <wbr>Bone <wbr>Collector

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³¹).

 1 /*  
 2 //0-1背包问题，容量可以从前向后推（二维数组），也可以从后向前推（一维数组） 
 3 
 4 //代码一：
 5 #include<stdio.h>
 6 #include<string.h>
 7 int main()
 8 {
 9     int t,V,i,j,N;
10     int val[1001],vol[1001],record[1001];
11     scanf("%d",&t);
12     while(t--)
13     {
14         memset(record,0,sizeof(record));
15         scanf("%d%d",&N,&V);
16         for(i=0;i<N;++i)
17             scanf("%d",&val[i]);
18         for(i=0;i<N;++i)
19             scanf("%d",&vol[i]);
20         for(i=0;i<N;++i)
21             for(j=V;j>=vol[i];--j)
22                 if(record[j-vol[i]]+val[i]>record[j])
23                     record[j]=record[j-vol[i]]+val[i];
24         printf("%d\n",record[V]);
25     }
26     return 0;
27 }
28 
29 
30 //代码二：
31 #include<stdio.h>
32 #include<string.h>
33 int main()
34 {
35     int t,V,i,j,N;
36     int val[1001],vol[1001],record[1001];
37     scanf("%d",&t);
38     while(t--)
39     {
40         memset(record,0,sizeof(record));
41         scanf("%d%d",&N,&V);
42         for(i=0;i<N;++i)
43             scanf("%d",&val[i]);            
44         for(i=0;i<N;++i)
45         {
46             scanf("%d",&vol[i]);
47             for(j=V;j>=vol[i];--j)
48                 if(record[j-vol[i]]+val[i]>record[j])
49                     record[j]=record[j-vol[i]]+val[i];
50         }
51         printf("%d\n",record[V]);
52     }
53     return 0;
54 }
55 */
56 
57 //代码三：   二位数组的写法
58 #include<stdio.h>
59 #include<string.h>
60 
61 int val[1001],vol[1001];
62 int dp[1001][1001];
63 int main()
64 {
65     int T,i,j,n,v;
66     scanf("%d",&T);
67     while(T--)
68     {
69         scanf("%d%d",&n,&v);
70         for(i=1;i<=n;++i)
71             scanf("%d",&val[i]);
72         for(i=1;i<=n;++i)
73             scanf("%d",&vol[i]);
74         memset(dp,0,sizeof(dp));
75         for(i=1;i<=n;++i)
76             for(j=0;j<=v;++j)     //注意这里要从0开始
77                 if(j>=vol[i])     //背包容量能过装下第i件骨头的情况下选取装与不装的最大值
78                     dp[i][j]=dp[i-1][j]>dp[i-1][j-vol[i]]+val[i]?dp[i-1][j]:dp[i-1][j-vol[i]]+val[i];
79                 else               //背包容量不能装下第i件的化当前最大值为装下前i-1件骨头的状态
80                     dp[i][j]=dp[i-1][j];
81         printf("%d\n",dp[n][v]);
82     }
83     return 0;
84 }

功不成，身已退