Leaky Cauldron
0%

限重最大值问题

Posted on Edited on

题目

给定两个数组 w 和 v ，两个数组长度相等，w[i] 表示第i件商品的 重量，v[i] 表示第i件商品的价值。 再给定一个整数 bag ，要求你挑选商品的重量加起来一定不能超过 bag ，返回满足这个条件下，你能获得的最大价值。

题解

解法类似上一篇博客

暴力递归

穷举所有可能的结果, 迭代过程中判断累计重量 acc_weight 是否超过 bag , 若超过则返回 Integer.MIN_VALUE , 相当于直接舍弃该分支. 另一个迭代的基础条件为当 i 达到 w.length 时, 返回 0 , 因为第 i 次递归的返回值为当前商品的价值 v[i] 加上后续商品的价值与只有后续商品价值二者中的较大者, i 等于 w.length 时, 没有后续商品, 故直接返回 0 .

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
public class Knapsack {
    public static int maxValue(int[] w, int[] v, int i, int accWeight, int bag) {
        if (accWeight > bag) {
            return Integer.MIN_VALUE;   // 重量超过 bag, 舍弃
        }

        if (i == w.length) {
            return 0;
        }

        return Math.max(
                maxValue(w, v, i + 1, accWeight, bag),
                v[i] + maxValue(w, v, i + 1, accWeight + w[i], bag)
        );
    }

    public static void main(String[] args) {
        int[] w = {3, 2, 4, 7};
        int[] v = {5, 6, 3, 19};
        int bag = 11;

        System.out.println(maxValue(w, v, 0, 0, bag));
    }
}
Python
1
2
3
4
5
6
7
8
9
def max_value(w, v, i, acc_weight, bag):
    if acc_weight > bag: return float('-inf')

    if i == len(w): return 0

    return max(
        max_value(w, v, i + 1, acc_weight, bag),
        v[i] + max_value(w, v, i + 1, acc_weight + w[i], bag)
    )

动态规划

此类无后效性的递归问题均可转化为动态递归.

步骤
  1. 分析可变参数, 求出表空间
  2. 确定最终状态
  3. 根据 base case 确定初始状态
  4. 分析一个普遍位置的依赖关系
  5. 根据依赖顺序, 逆序求出整张表
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Knapsack {
    public static int maxValue(int[] w, int[] v, int bag) {
        int[][] dp = new int[w.length + 1][bag + 1];

        for (int i = 0; i <= bag; i++) {
            dp[w.length][i] = 0;
        }

        for (int i = w.length - 1; i >= 0; i--) {
            for (int j = bag; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (j + w[i] <= bag)
                    dp[i][j] = Math.max(
                            dp[i + 1][j],
                            dp[i + 1][j + w[i]] + v[i]
                    );
            }
        }

        return dp[0][0];
    }
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def max_value(w, v, bag):
    dp = [[0] * (bag + 1) for _ in range(len(w) + 1)]

    for i in range(len(w) - 1, -1, -1):
        for j in range(bag, -1, -1):
            dp[i][j] = dp[i + 1][j]
            if j + w[i] <= bag:
                dp[i][j] = max(
                    dp[i + 1][j],
                    dp[i + 1][j + w[i]] + v[i]
                )
                
    return dp[0][0]