媒介

接着上一篇一道题看清动态筹划的前世此生(一)，这次我们会以同样的思路去阐明经典的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);
}