动态规划——01背包问题

动态规划——01背包问题

动态规划问题是算法学习过程中的一大难点，如果说动态规划是一座桥，那么背包问题无疑是顶起桥梁的石柱。本篇文章将详细的为您讲诉背包问题中的几个重要的模型，希望您学习愉快。
动态规划问题的一般性解题步骤可分为以下几步：
1、简化问题
2、找出关系数组
3、列出递推表达式
4、寻找解组成

01背包

01背包 的特征主要是物品至多只能选一个，也就是对于每个物品，要么选，要么不选。

1、问题描述

下面给出一个例题

有一个小偷，他有一个容量为 V 的背包，在小堕落街有 N 个小店，每个店可获取体积为 v_i ，价值为 w_i 的物品 。这个小偷想尽可能多地使价值最大化，问小偷能获取地最大价值是多少？

2、算法思路

根据一般性解题步骤：
1、简化问题
所谓简化问题即将原问题转化为更一般性地，更易理解地问题。

原问题可化为：从 N 个物品中挑选 k (0 <= k <= N)个物品使获取价值最大并且总体积不超过 V ，每个物品体积为 v_i ,价值为 w_i 。

原问题规模较大的复杂模型难以求解，我们可将其化为比原问题规模更小的子问题来求解。对于 N 个物品难以求解，我们可以猜想我们是否可以先求解出前 N-1 个物品，总体积为不超过 V 能获取的最大价值，然后在分析第 N 个物品是否可以选择呢？答案是肯定的。由此前 N-1 个物品的最大价值也可由前 N-2 个物品所确定，依次类推，我们只需分析第 i 个物品的选择与否即可。具体第 3 点有详细解答。

2、找出关系数组
找出关系数组即定义用来存储答案的数组，需要注意的是定义数组时要明确数组的含义，使其更易于找出递推表达式以及更易于表示答案。

这里我们定义数组为dp[i][j]，表示到第 i 个小店为止，体积为 j 的最大价值 。

3、列出递推表达式
递推表达式又称 动态转移方程 ，即某个状态下的答案表示式。
对于第 N 个物品，我们可以考虑选与不选两种情况，不选情况下的最大价值即为前 N-1 个物品，体积不超过 V 的最大价值。选的情况下，前 N 个物品的剩余背包容量要装得下第 N 个物品，即总体积不超过 V-v_N ，最大价值即为前 N 个物品，体积不超过 V-v_N 得最大价值加上第 N 个物品得价值。根据我们的算法思路可知，对于第 i 个物品能获取的最大价值，我们总是能先计算出第 i-1 个物品的最大价值。由此，算法的正确性也得到了证明。
下面给出详细表达式 ：
我们考虑到第 i 个物品，体积为 j 时，对第 i 个物品，不选得情况下，价值为dp[i-1][j]；选择的情况下，价值即为dp[i][j-v_i] + w_i。现在我们求出这两种情况下的最大价值，对于第 i 个物品，体积为 j 的最大价值即 dp[i][j] = max(dp[i-1][j],dp[i-1][j-v_i] + w_i） 。

3、基本代码

#include <iostream>
using namespace std;

int dp[1010][1010];
int v[1010],w[1010];

int main()
{
	int N,V;cin >> N >> V;
	for(int i = 1;i <= N;i++)cin >> v[i] >> w[i];
	
	for(int i = 1;i <= N;i++)//从第一个物品开始考虑
	{
		for(int j = 0;j <= V;j++)//体积从 0 开始
		{
			//能选择的情况，需考虑是否装得下第i个物品
			if(j >= v[i])dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]] + w[i]);
			else dp[i][j] = dp[i-1][j];//装不下的情况，第i个物品的最大价值就是第i-1个物品的最大价值
		}
	}
	cout << dp[N][V] << '\n';
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4、优化

01背包的优化主要是对于空间的优化，一般情况下的01背包模型所使用的dp数组是二维的，对空间要求较高，如果 N 很大或者 V 很大时，二维dp数组可能直接就寄了，那我们是否可以将其优化至一维呢？

对于动态转移方程 dp[i][j] = max(dp[i-1][j],dp[i-1][j-v_i] + w_i） ，我们观察到，每一个 i 的答案只与 i-1 有关， 而之前的维度再无可用之地了，那我们是否可以将其删去呢？这是当然可以的。这样，我们就只需要两个一维即可解决问题。

#include <iostream>
using namespace std;

int dp[1010][2];
int v[1010],w[1010];

int main()
{
	int N,V;cin >> N >> V;
	for(int i = 1;i <= N;i++)cin >> v[i] >> w[i];
	
	for(int i = 1;i <= N;i++)//从第一个物品开始考虑
	{
		int y = i % 2;
		for(int j = 0;j <= V;j++)//体积从 0 开始
		{
			//这里的y ^ 1是位运算，即当y = 0时，y ^ 1 = 1；当y = 1时，y ^ 1 = 0
			//更精确的解释，y是当前状态，y ^ 1是上一个状态
			if(j >= v[i])dp[y][j] = max(dp[y ^ 1][j],dp[y ^ 1][j-v[i]] + w[i]);
			else dp[y][j] = dp[y ^ 1][j];
		}
	}
	cout << dp[N & 1][V] << '\n';
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

再观察一下，我们还可以发现对于每一维，它总是在上一维的基础上发生转移，并且不会改变下一维，由此我们可以直接在上一维进行操作来作为下一维的答案。我们将其推广到每一维上，这样我们就可以将其优化到一维了。但是这样就对了吗？不是的。当我们将体积从 0 到 V 进行遍历时，操作一个状态其前一个状态已经发生改变了，而我们所需要的答案是不需要改变的。我们可以怎样在改变上后一个状态的同时保证前一个状态不发生改变呢，我们可以从后往前遍历，即从 V 遍历到 0 ，这样就得到了一维形式下的01背包模型了。

#include <iostream>
using namespace std;

int dp[1010];
int v[1010],w[1010];

int main()
{
	int N,V;cin >> N >> V;
	for(int i = 1;i <= N;i++)cin >> v[i] >> w[i];
	
	for(int i = 1;i <= N;i++)//从第一个物品开始考虑
	{
		for(int j = V;j >= 0;j--)//体积从 V 开始
		{
			dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
		}
	}
	cout << dp[V] << '\n';
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

好了，01背包的讲解到此结束，望各位学习愉快！