01背包问题

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

# 未完成

01背包问题详解

01背包是一种动态规划问题。动态规划的核心就是状态转移方程，本文主要解释01背包状态转移方程的原理。

问题描述

01背包问题可描述为如下问题：
有一个容量为V的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。
问：如何向背包装物体才能使背包中物体的总价值最大？

为什么不用贪心？

我在第一次做这个题目时考虑的是贪心算法。所谓贪心问题，就是每一步决策都采取最优解，按照此方案最后结果也是最优解。
为什么这个问题不能用贪心呢？
举个例子
我的背包容量为10，而且有4个物体，它们的体积和价值分别为
w1 = 8, v1 = 9
w2 = 3, v2 = 3
w3 = 4, v3 = 4
w4 = 3, v4 = 3
贪心是每一步采取最优拿法，即每一次都优先拿价值与体积比值最大的物体
c1 = v1/w1 = 1.125（最大）
c2 = v2/w2 = 1
c3 = v3/w3 = 1
c4 = v4/w4 = 1
所以优先拿第一个物体，随后背包再也装不下其他物体了，则最大价值为9。
但是这个问题的最优解是取物体2，3，4装进背包，最大价值为3+4+3=10！！！
所以这个问题不可以用贪心法来处理。

原始的 01背包

01背包的状态转移方程为
`f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[j])

i代表对i件物体做决策，有两种方式—放入背包和不放入背包。
j表示当前背包剩余的容量。

转移方程的解释：
创建一个状态矩阵f，横坐标 i 是物体编号，纵坐标 j 为背包容量。
首先将 f 第0行和第0列初始化为0 （代码里面将整个f初始化为0了，其实只初始化第0行和第0列就够了）。这个表示不放物体时最大价值为0 。（物体编号从1开始）
接下来依次遍历f的每一行。如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 1; i <= n; i++)
{
	for (int j = V; j >= 0; j--)
	{
		if (j >= w[i])//如果背包装得下当前的物体
		{
			f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
		}
		else//如果背包装不下当前物体
		{
			f[i][j] = f[i - 1][j];
		}
	}
}

如果背包装得下当前的物体，在遍历过程中分别计算第i件物体放入和不放入背包的价值，取其中大的做为当前的最大价值。
如果背包装不下当前物体那么第i个物体只有不放入背包一种选择。

不放入背包时:第i次决策后的最大价值和第i-1次决策时候的价值是一样的（还是原来的那些物体，没多没少）。
放入背包时:第i次决策后的价值为 第i-1次决策时候的价值 加上 当前物体的价值v[j]。物体放入背包后会使背包容量变为 j ，即没放物体之前背包的容量为j - w[i]。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
using namespace std;
#define max(N1,N2) N1>N2?N1:N2
int main()
{
	/*
	第一行输入背包容量V和物体的个数n
	接下来有n行，每行包含两个数字，分别为该物体的花费和价值
	*/
	vector<int> w, v;//w为花费，v为价值
	vector<vector<int>> f;//f状态矩阵
	int V, n;//V背包容量，n物体数
	while (cin >> V >> n)
	{
		w.clear();
		v.clear();
		f.clear();
		w.push_back(0);
		v.push_back(0);

		//输入原始数据
		for (int i = 1; i <= n; i++)
		{
			int cur_w, cur_v;
			cin >> cur_w >> cur_v;
			w.push_back(cur_w);
			v.push_back(cur_v);
		}

		//初始化状态矩阵
		for (int i = 0; i <= n; i++)
		{
			vector<int> buff(V + 1, 0);
			f.push_back(buff);
		}

		//动态规划过程
		for (int i = 1; i <= n; i++)
		{
			for (int j = V; j >= 0; j--)
			{
				if (j >= w[i])
				{
					f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
				}
				else
				{
					f[i][j] = f[i - 1][j];
				}
			}
		}

		//输出答案
		int ans = f[n][V];
		cout << ans << endl;
	}
	return 0;
}

Reference

01背包问题详解（浅显易懂）-CSDN博客