算法之名——动态规划（01背包）

vlambda
2020-05-09

算法之名——动态规划（01背包）

01背包是动态规划问题中的一类典型问题。

最基本问题框架是有n 个物品，它们有各自的体积和价值，现有给定容量m的背包，如何让背包里装入的物品具有最大的价值总和？

这类问题可以考虑使用动态规划求解，动态规划的核心步骤这里就不再赘述。

我们假设这里n=4，m=6。

n	1	2	3	4
v(价值)	1	2	3	4
c(体积)	1	2	3	4

dp[i][j]表示取到第i个物品，并且背包此时装的总量为j时的最大价值。

接下来我们需要推导最关键的递推公式

当背包容量j小于Vi的时候，我们不能将物品i放入背包

这里我们很容易可以得到dp[i][j]=dp[i-1][j];

当背包容量j大于等于Vi的时候，我们有两个选择

不放入背包时，dp[i][j]=dp[i-1][j];

放入背包时，dp[i][j]=dp[i-1][j-c[i]]+v[i];

这里我们要两者取其大，可以得到递推公式

dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);

这样我们就可以得到如下dp表格（行为物品i，列为背包容量j）

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	1	2	3	3	3	3
3	1	2	3	4	5	6
4	1	2	3	4	5	6

dp[n][m]的值就是我们要得到的最大价值

这样我们可以得到如下核心代码

for(int i=1;i<=n;i++){        for(int j=0;j<=m;j++){ if(w[i]>j) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } }

使用二维数组解决01背包问题的时间复杂度和空间复杂度都为O(n*m)。

优化空间复杂度

其实我们可以使用一维数组来代替二维数组，将空间复杂度降低为O(m)。

我们观察上面的dp表格，可以发现我们其实最后只是用到了最后一行，其他的都是为了推导出最后一行，所以我们想一下是不是可以直接使用一个一维数组来代替之前的二维数组。答案是肯定的，这里理解起来可能有点难度，我们可以参考求斐波那契数列第i项时使用数组和不使用数组的解法的思维方式。

如果第i个物品放入背包

dp[j]=dp[j-c[i]]+v[i]

如果不放入背包，那么dp[j]的值不需要改编

dp[j]=dp[j]

我们可以得到如下公式

dp[j]=max(dp[j-c[i]]+v[i],dp[j])

这里需要注意一点，内层循环必须是倒序的。

因为我们要保证, 在第i次外循环时, 调用的dp[j-c[i]]实际上是基于第i-1次循环得到的值。而逆序保证了, 对于dp[j], 它要调用的dp[j-c[i]]一定是第i层循环还没有更新过的, 换言之, dp[j-c[i]]只有可能是第i-1层存储的数据.

这样我们可以得到优化后的核心代码

for(int i=1;i<=n;i++){        for(int j=m;j>=c[i];j--)            dp[j]=max(dp[j],dp[j-c[i]]+v[i]);

dp[m]就是我们要得到的答案。

下面是一道例题

HDU-2602

http://acm.hdu.edu.cn/showproblem.php?pid=2602

01背包的模板问题，直接按照上面给出的核心代码就可以ac

// 二维数组#include<bits/stdc++.h>#define mem(arr,p) memset(arr,p,sizeof(arr))typedef long long ll;using namespace std;bool space;void print(){if(space)cout<<" ";space=true;}const int MAXN=1002;ll dp[MAXN][MAXN],w[MAXN],v[MAXN];int find_MAX(int N,int V){ for(int i=1;i<=N;i++){ for(int j=0;j<=V;j++){ if(w[i]>j) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } } return dp[N][V];}int main(){ int T; cin>>T; while(T--){ int N,V; cin>>N>>V; mem(dp,0); for(int i=1;i<=N;i++) cin>>v[i]; for(int i=1;i<=N;i++) cin>>w[i]; cout<<find_MAX(N,V)<<endl; }}/*15 101 2 3 4 55 4 3 2 1*/   // 一维数组空间优化#include<bits/stdc++.h>#define mem(arr,p) memset(arr,p,sizeof(arr))typedef long long ll;using namespace std;bool space;void print(){if(space)cout<<" ";space=true;}const int MAXN=1005;int dp[MAXN],w[MAXN],v[MAXN];int find_MAX(int N,int V){ for(int i=1;i<=N;i++){ for(int j=V;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } return dp[V];}int main(){ int T; cin>>T; while(T--){ int N,V; cin>>N>>V; mem(dp,0); for(int i=1;i<=N;i++) cin>>v[i]; for(int i=1;i<=N;i++) cin>>w[i]; cout<<find_MAX(N,V)<<endl; }}