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

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

前言

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

经典01背包问题

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

暴搜出奇迹

继续我们上一篇的套路来一步一步逼近我们要的动态规划的解法。
假设我们完成了暴搜的函数，我们只需返回结果！

java版

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版

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版

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版

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)

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

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版

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版

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版

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版

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]

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