这一节我们介绍使用动态规划解决的一个非常经典的问题：0-1 背包问题。
0-1 背包问题描述
问题描述：
有一个背包，它的容量为
(Capacity)。现在有
种不同的物品，编号为
，其中每一件物品的重量为
，价值为
。问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最大。
这个问题其实是一个有约束的最优化问题。
思路1：暴力解法。
我们最容易想到的是暴力解法，因为每一件物品都可以放进背包，也可以不放进背包，这样 件物品就有
种选择，再对这
种选择遍历选出最大值。因此如果使用暴力解法，算法的时间复杂度为
。显然，暴力解法是不可行的。
思路2：贪心算法。
那么，我们是否可以使用贪心算法呢？基于贪心算法的规则，我们优先放入平均价值（单位价值）最高的物品？其实，这样的策略是有问题的。可以很容易地举出反例说明贪心算法是行不通的，事实上，使用贪心解决该问题也缺乏理论依据。
那么我们对这个问题可以挖掘出哪些特点？这是一个组合问题，组合问题可以使用搜索的方法求解，进而看看在这个问题是否有重叠子问题、最优子结构。画图，进而发现使用递归，发现有重叠子问题，使用记忆化递归。
第 1 步：定义状态。
首先寻找状态，即设定一个递归函数，这个递归函数要完成什么事情，需要哪些参数，参数的个数通常是约束条件的个数。
的定义：选择索引的区间范围是
内的物品，填充容积为
的背包的最大价值。
考虑将 个物品放进容量为
的背包，使得价值最大。
第 2 步：推导出状态转移方程。
于是对于 ，
有以下两种方案：
1、第 个物品没有被选择，则
为所求；
2、第 个物品被选择，则
为所求。
综合以上两点： 为所求，这个方程就称为状态转移方程。
以上的这种求解问题的思路，是自顶向下的思路，之后我们再把它改造成自底向上的动态规划问题的求解方式。
我们选择使用递归的方式来解决这个问题，这个问题含有重叠子问题，所以我们必须为这个递归方法加上“缓存”，即实现“记忆化递归”。注意：缓存是一个二维数组。记忆化的空间应该是一个二维数组，因为是 和
的组成的数据对，所以有
行，
列。记忆化递归的写法是一个套路，一定要熟练。下面我们介绍在二维数组中，自底向上使用动态规划解决背包问题。一行一行填写表格（表格的意义也要非常清楚），就能发现规律。用一个非常小的数值发现程序中的数值是如何变化的。从索引
[0][0] 到索引 [n-1][C]。状态使用了两个参数来定义。
下面举例说明：
| id | 0 | 1 | 2 |
|---|---|---|---|
| weight | 1 | 2 | 3 |
| value | 6 | 10 | 12 |
下面我们自底向上通过填表来完成这个问题：容量为 5 的时候。
| id/C | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 6 | 6 | 6 | 6 | 6 |
| 1 | 0 | 6 | 10 | 16 | 16 | 16 |
| 2 | 0 | 6 | 10 | 16 | 18 | 22 |
其实我们填写每一行的时候，只参考了上一行的结果，这一点对于我们思考这个问题和用代码实现来说都是非常重要的。
使用递归解决 0-1 背包问题
首先是这个问题的框架：
Python 代码：
class Solution:
def knapsack01(self, weights, values, C):
pass
if __name__ == '__main__':
pass
在思路非常清楚的情况下，是可以很轻松地写出代码的。
Python 代码：
class Solution:
def __init__(self):
self.cache = []
def _best_value(self, weights, values, index, capacity):
'''
写出状态转移方程以后，就可以马上写出代码了
f(index,capacity) = max(f(index-1,capacity), # 这个物品不拿
v(index) + f(index-1,capacity-w(index))) # 拿了这个物品，**前提是背包能装下这个物品**
注意点：
+ 要记得判断这个背包能不能放下这第 index 个物品
+ 用了递归，递归终止的条件要想清楚
+ 最后不要忘记加上缓存
:param weights:
:param values:
:param index: index 表示物品的编号
:param capacity: capacity 表示背包的最大容量
:return:
'''
# 注意临界条件
if index < 0 or capacity <= 0:
return 0
if self.cache[index][capacity] != -1:
return self.cache[index][capacity]
# 候选值
res = self._best_value(weights, values, index - 1, capacity)
if weights[index] <= capacity:
res = max(res, values[index] + self._best_value(weights, values, index - 1, capacity - weights[index]))
self.cache[index][capacity] = res
return res
def knapsack01(self, weights, values, C):
l = len(weights)
if l == 0:
return 0
self.cache = [[-1 for _ in range(C + 1)] for _ in range(l)]
return self._best_value(weights, values, l - 1, C)
Java 代码：
/**
* 0-1 背包问题递归版（没有加上记忆化搜索）
* Created by liwei on 17/10/4.
*/
public class Solution {
public int knapsack01(int[] w, int[] v, int C) {
assert (w.length == v.length && C >= 0);
int len = w.length;
if (len == 0 || C == 0) {
return 0;
}
int res = bestValue(w, v, w.length - 1, C);
return res;
}
// 在 [0,...,index] 这个区间里，选取物品，获得的价值最大值
private int bestValue(int[] w, int[] v, int index, int C) {
if (index < 0 || C <= 0) {
return 0;
}
int res = bestValue(w, v, index - 1, C);
if (C >= w[index]) {
res = Integer.max(res, v[index] + bestValue(w, v, index - 1, C - w[index]));
}
return res;
}
public static void main(String[] args) {
int[] weight = new int[]{1, 2, 3};
int[] value = new int[]{6, 10, 12};
int C = 5;
Solution solution = new Solution();
int maxValue = solution.knapsack01(weight, value, C);
System.out.println(maxValue);
}
}
使用记忆化递归解决 0-1 背包问题
Java 代码：
/**
* 0-1 背包问题 加上了记忆化递归
* Created by liwei on 17/10/4.
*/
public class Solution1 {
private int[][] memory;
public int knapsack01(int[] w, int[] v, int C) {
assert (w.length == v.length && C >= 0);
int len = w.length;
if (len == 0 || C == 0) {
return 0;
}
memory = new int[len][C + 1];
for (int i = 0; i < len; i++) {
for (int j = 0; j < C + 1; j++) {
memory[i][j] = -1;
}
}
int res = bestValue(w, v, w.length - 1, C);
return res;
}
// 在 [0,...,index] 这个区间里，选取物品，获得的价值最大值
private int bestValue(int[] w, int[] v, int index, int C) {
if (index < 0 || C <= 0) {
return 0;
}
if (memory[index][C] == -1) {
int res = bestValue(w, v, index - 1, C);
if (C >= w[index]) {
res = Integer.max(res, v[index] + bestValue(w, v, index - 1, C - w[index]));
}
memory[index][C] = res;
}
return memory[index][C];
}
public static void main(String[] args) {
int[] weight = new int[]{1, 2, 3};
int[] value = new int[]{6, 10, 12};
int C = 5;
Solution1 solution = new Solution1();
int maxValue = solution.knapsack01(weight, value, C);
System.out.println(maxValue);
}
}
使用动态规划解决 0-1 背包问题
Python 代码：动态规划
class Solution:
def knapsack01(self, weights, values, capacity):
'''
一行一行填表
# 填写第 0 行（只有 index = 0 这个物品）的时候，就看这个 index 的物品是否能放进背包
# 如果可以放进背包，就是此时的最大价值
:param weights:
:param values:
:param index:
:param capacity:
:return:
'''
l = len(weights) # 有多少个物品
if l == 0:
return 0
dp = [[-1 for _ in range(capacity + 1)] for _ in range(l)]
# 先写第 1 行
for i in range(capacity + 1):
if weights[0] <= i:
dp[0][i] = values[0]
else:
dp[0][i] = 0
# 然后写后面几行
for i in range(1, l):
for j in range(capacity + 1):
# 首先不考虑拿这个物品，我们把上一行抄下来就可以了
dp[i][j] = dp[i - 1][j]
# 如果考虑拿这个物品，我们就要判断这个物品能不能装进背包
if weights[i] <= j:
dp[i][j] = values[i] + dp[i - 1][j - weights[i]]
return dp[-1][-1]
Java 代码：
/**
* 0-1 背包问题 动态规划解法
* Created by liwei on 17/10/4.
*/
public class Solution2 {
private int[][] memory;
public int knapsack01(int[] w, int[] v, int C) {
assert (w.length == v.length && C >= 0);
int len = w.length;
if (len == 0 || C == 0) {
return 0;
}
memory = new int[len][C + 1];
for (int j = 0; j < C + 1; j++) {
memory[0][j] = w[0] > j ? 0 : v[0];
}
for (int i = 1; i < len; i++) {
for (int j = 0; j < C + 1; j++) {
memory[i][j] = memory[i - 1][j];
if (w[i] <= j) {
memory[i][j] = Integer.max(memory[i][j], v[i] + memory[i - 1][j - w[i]]);
}
}
}
return memory[len - 1][C];
}
public static void main(String[] args) {
int[] weight = new int[]{1, 2, 3};
int[] value = new int[]{6, 10, 12};
int C = 5;
Solution2 solution = new Solution2();
int maxValue = solution.knapsack01(weight, value, C);
System.out.println(maxValue);
}
}
（本节完）
网友评论