01背包模板

一、动态规划：
如果一句话总结的的话，我觉得dp是这样的：
动态规划是用空间换时间的一种方法的抽象，其关键是发现子问题和记录其结果，然后利用这些结果减轻运算量。

二、01背包思路：
主要的有两点：
1 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
2

三、代码：

以HDU2602为例
1 二维递推版

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 const int maxn=1005;
 7 
 8 int dp[maxn][maxn];
 9 
10 int va[maxn],vo[maxn];
11 
12 int getmax(int a,int b)
13 {
14     if(a>=b)
15         return a;
16     else
17         return b;
18 }
19 
20 int main()
21 {
22     int n,all;
23     int t;
24     cin>>t;
25     while(t--){
26         cin>>n>>all;
27         for(int i=1;i<=n;i++)
28             cin>>va[i];
29         for(int i=1;i<=n;i++)
30             cin>>vo[i];
31         dp[0][0]=0;
32         for(int i=1;i<=n;i++)
33         {
34             for(int j=0;j<=all;j++)
35             {
36                 if(j-vo[i]<0)
37                     dp[i][j]=dp[i-1][j];
38                 else
39                     dp[i][j]=getmax(dp[i-1][j],dp[i-1][j-vo[i]]+va[i]);
40             }
41         }
42         cout<<dp[n][all]<<endl;
43     }
44     return 0;
45 }

View Code

2 一维递推版

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int dp[1001];
 6 int vo[1001];
 7 int va[1001];
 8 
 9 int main()
10 {
11     int n,all;
12     int t;
13     cin>>t;
14     while(t--)
15     {
16         memset(dp,0,sizeof(dp));
17 
18         cin>>n>>all;
19         for(int i=1;i<=n;i++)
20             cin>>va[i];
21         for(int i=1;i<=n;i++)
22             cin>>vo[i];
23         for(int i=1;i<=n;i++)
24         {
25             for(int j=all;j>=0;j--)
26             {
27                 if(j-vo[i]>=0)
28                 dp[j]=max(dp[j],dp[j-vo[i]]+va[i]);
29             }
30         }
31         cout<<dp[all]<<endl;
32     }
33     return 0;
34 }

View Code

3 递归版（一直wrong尚未找出错误原因）

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 const int maxn=1001;
 6 
 7 int va[maxn],vo[maxn],dp[maxn][maxn];
 8 
 9 int ddp(int i,int v)
10 {
11     if(dp[i][v]!=-1)
12         return dp[i][v];
13     if(i==0||v==0)
14         return dp[i][v]=0;
15     if(v-vo[i]>=0)
16         return dp[i][v]=max(ddp(i-1,v),ddp(i-1,v-vo[i])+va[i]);
17     else
18         return dp[i][v]=ddp(i-1,v);
19 }
20 
21 int main()
22 {
23     int n,all;
24     int t;
25     cin>>t;
26     while(t--)
27     {
28         cin>>n>>all;
29         for(int i=1;i<=n;i++)
30             cin>>va[i];
31         for(int i=1;i<=n;i++)
32             cin>>vo[i];
33         memset(dp,-1,sizeof(dp));
34         cout<<ddp(n,all)<<endl;
35     }
36     return 0;
37 }

View Code

终于知道哪里错了，物品体积为0

所以递归中 v==0去掉就可以了。

四、题目：

HDU2602

hrbust1558小背包