一道题看清动态规划的前世今生(二)

@author: StormMa
@date 2017-11-16


生命不息,奋斗不止

前言

接着上一篇一道题看清动态规划的前世今生(一),这次我们会以同样的思路去分析经典的01整数背包问题,加深对动态规划的印象。

经典01背包问题

给定n种物品和一个背包。物品i的重量是w[i],其价值位v[i] ,背包的容量为W。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大?

暴搜出奇迹

继续我们上一篇的套路来一步一步逼近我们要的动态规划的解法。

假设我们完成了暴搜的函数,我们只需返回结果!

java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int search(int idx, int[] w, int[] v, int n, int s, int W) {
...
}
/**
* @param w 物品重量
* @param v 物品价值
* @param W 背包的最大容量
* @return 最大价值
*/
public int solve(int[] w, int[] v, int W) {
int n = w.length;
return search(0, w, v, n, 0, W);
}

python版

1
2
3
4
5
6
def search(self, idx, w, v, n, s, W):
pass
def solve(w, v, W):
n = len(w)
return self.search(0, w, v, n, 0, W)

上面的代码,search()函数的idx代表从几号元素开始搜索,s表示,背包已经装了s重量的物品。

那么,很简单,每个物品的状态只有两种,一种就是放入背包,一种就是不放,我们取这两种最大价值的那一个情况,返回即可,很容易完成search()函数的方法体。

java版

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
private int search(int idx, int[] w, int[] v, int n, int s, int W) {
// 已经没有物品搜索了
if (idx >= n) {
return 0;
}
// 如果装不下这件物品,直接返回不拿这件物品的重量即可
if (s + w[idx] > W) {
return search(idx + 1, w, v, n, s, W);
}
// 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
return Math.max(search(idx + 1, w, v, n, s + w[idx], W) + v[idx], search(idx + 1, w, v, n, s, W));
}
/**
* @param w 物品重量
* @param v 物品价值
* @param W 背包的最大容量
* @return 最大价值
*/
public int solve(int[] w, int[] v, int W) {
int n = w.length;
return search(0, w, v, n, 0, W);
}

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def search(self, idx, w, v, n, s, W):
# 如果已经搜索完了所有的物品
if idx >= n:
return 0
# 如果装不下这件物品,直接返回不拿这件物品的重量即可
if s + w[idx] > W:
return self.search(idx + 1, w, v, n, s, W)
# 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
return max(self.search(idx + 1, w, v, n, s, W), self.search(idx + 1, w, v, n, s + w[idx], W) + v[idx])
def solve(w, v, W):
n = len(w)
return self.search(0, w, v, n, 0, W)

关于暴搜代码很简单,只要我们对递归足够了解,我们就很容易写出暴搜!

记忆化搜索

如果看过我前一篇博客的人,大概都知道,下来我们要对状态进行删减,因为上面的代码我们出现了重复计算!你能看出在哪我们重复计算了吗?

假如我们要计算5个物品的最大价值:

w[5] = {4, 3, 2, 5, 1}
v[5] = {3, 4, 1, 4, 2}
W = 10

为了方便起见,search()函数我们简化为f(idx, S)

然后我们的计算过程应该是这样

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
f(0, 0) = {
f(1, 4) = {
f(2, 7) = {
f(3, 9) = { // ======>
...
},
f(3, 7) = {
...
}
},
f(2, 4) = {
f(3, 4) = {
...
},
f(3, 9) = { // ======>
...
}
}
},
f(1, 0) = {
f(2, 0) = {
...
},
f(2, 3) = {
...
}
}
}

通过上面的验算,我们很容易看出来,f(3, 9)我们计算了两次,所以这就是重复状态,我们应该用个二维数组来存储[idx][S]的值,后面用到直接返回我们上次搜索的结果即可!对吧?我想应该是对的,我相信你也是同意我的!

java版

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
private int search(int idx, int[] w, int[] v, int n, int s, int W, int[][] memo) {
// 已经没有物品搜索了
if (idx >= n) {
return 0;
}
if (memo[idx][s] != -1) {
return memo[idx][s];
}
// 如果装不下这件物品
if (s + w[idx] > W) {
return memo[idx][s] = search(idx + 1, w, v, n, s, W, memo);
}
// 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
return memo[idx][s] = Math.max(search(idx + 1, w, v, n, s + w[idx], W, memo) + v[idx], search(idx + 1, w, v, n, s, W, memo));
}
/**
* @param w 物品重量
* @param v 物品价值
* @param W 背包的最大容量
* @return 最大价值
*/
public int solve(int[] w, int[] v, int W) {
int n = w.length;
final int[][] memo = new int[n][W + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= W; j++) {
memo[i][j] = -1;
}
}
return search(0, w, v, n, 0, W, memo);
}

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def search(self, idx, w, v, n, s, W, memo):
# 如果已经搜索完了所有的物品
if idx >= n:
return 0
# 如果装不下这件物品,直接返回不拿这件物品的重量即可
if memo[idx][s] != -1:
return memo[idx][s]
if s + w[idx] > W:
memo[idx][s] = self.search(idx + 1, w, v, n, s, W, memo)
return memo[idx][s]
# 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
memo[idx][s] = max(self.search(idx + 1, w, v, n, s, W, memo),
self.search(idx + 1, w, v, n, s + w[idx], W, memo) + v[idx])
return memo[idx][s]
def solve(self, w, v, W):
n = len(w)
memo = [[-1 for i in range(W + 1)] for j in range(n)]
return self.search(0, w, v, n, 0, W, memo)

这就是dp了,我们把它改一下,改成递推形式的就是我们经常写的dp了

递推式记忆化搜索(dp)

java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int solve(int[] w, int[] v, int W) {
int n = w.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= W; j++) {
if (j < w[i]) {
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
return dp[n][W];
}

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
def solve(self, w, v, W):
n = len(w)
dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
for i in range(n):
for j in range(W + 1):
if j < w[i]:
dp[i + 1][j] = dp[i][j]
else:
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
return dp[n][W]

至于递推的顺序,从前到后还是从后到前,都是可以的,这个取决于个人的习惯!