M

M - 基础DP

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

Sample Output

14

//第一行代表有T个测试案例
第二行 n，m 代表有 n 个物品，背包容量为 m 。接下来两行分别是 n 个物品的价值，体积

//动态规划入门，看了很久才懂。
我先用的递归做的 5696kb 452ms

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAX 1005
 5 
 6 int v[MAX];
 7 int w[MAX];
 8 int f[MAX][MAX];
 9 
10 int max(int a,int b)
11 {
12     return a>b?a:b;
13 }
14 
15 int dp(int n,int m)
16 {
17     if (f[n][m]>=0) return f[n][m];
18 
19     if (n==0) return 0;
20 
21     if (m<v[n])//fang bu liao
22     {
23         return dp(n-1,m);
24     }
25     else
26     {
27         f[n][m]=f[n-1][m];
28         f[n][m]=max(dp(n-1,m),dp(n-1,m-v[n])+w[n]);
29     }
30     return f[n][m];
31 }
32 
33 int main()
34 {
35     int i,t,n,m;
36     scanf("%d",&t);
37     while (t--)
38     {
39         scanf("%d%d",&n,&m);
40         for (i=1;i<=n;i++)
41             scanf("%d",&w[i]);
42         for (i=1;i<=n;i++)
43             scanf("%d",&v[i]);
44 
45         memset(f,-1,sizeof(f));
46 
47             printf("%d
",dp(n,m));
48     }
49     return 0;
50 }

View Code

递推 5592kb 78ms

 1 #include <stdio.h>
 2 
 3 #define MAX 1005
 4 
 5 int v[MAX];
 6 int w[MAX];
 7 int f[MAX][MAX];
 8 
 9 int max(int a,int b)
10 {
11     return a>b?a:b;
12 }
13 
14 int main()
15 {
16     int i,j,t,n,m;
17     scanf("%d",&t);
18     while (t--)
19     {
20         scanf("%d%d",&n,&m);
21         for (i=1;i<=n;i++)
22             scanf("%d",&w[i]);
23         for (i=1;i<=n;i++)
24             scanf("%d",&v[i]);
25 
26         for (j=0;j<=m;j++) f[0][j]=0;
27 
28         for (i=1;i<=n;i++)
29             for (j=0;j<=m;j++)
30             {
31                 f[i][j]=f[i-1][j];
32                 if (j>=v[i])
33                     f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
34             }
35             printf("%d
",f[n][m]);
36     }
37     return 0;
38 }

View Code

一维数组 1784kb 15ms

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAX 1005
 5 
 6 int v[MAX];
 7 int w[MAX];
 8 int f[MAX];
 9 
10 int max(int a,int b)
11 {
12     return a>b?a:b;
13 }
14 
15 int main()
16 {
17     int i,j,t,n,m;
18     scanf("%d",&t);
19     while (t--)
20     {
21         scanf("%d%d",&n,&m);
22         for (i=1;i<=n;i++)
23             scanf("%d",&w[i]);
24         for (i=1;i<=n;i++)
25             scanf("%d",&v[i]);
26 
27         memset(f,0,sizeof(f));
28         for (i=1;i<=n;i++)
29             for (j=m;j>=0;j--)
30             {
31                 if (j>=v[i])
32                     f[j]=max(f[j],f[j-v[i]]+w[i]);
33             }
34             printf("%d
",f[m]);
35     }
36     return 0;
37 }

View Code