乐趣区

关于背包问题:关于01背包问题的解题思路

jiezi

有 N 件物品和一个最大分量为 W 的背包，每件物品分量 weight[i]，价值是 value[i]。每件物品只能取一次，背包能保留的最大价值是多少？

动静布局五部曲：

a) 确定 dp 数组以及下标的含意

b) 确定递推公式

c) dp 数组的初始化

d) 确定遍历程序

e) 举例推导 dp 数组

解题思路：

1) 确定 dp 数组以及下标的含意

dp[i][j]的定义为：从 0~i 的物品中任意取，背包容量为 j 的状况下价值总和最大是dp[i][j]

2) 递推公式

dp[i][j]从逻辑剖析上来看，有两个起源：即不放入物品 i，那么dp[i][j] = dp[i-1][j]（表明在 j 容量下，物品 i 所占分量对应的价值小于 0~i- 1 物品中选取的其余价值）。放入物品 i，dp[i][j] = value[i] + dp[i-1][j-weight[i]]

最终得出 dp[i][j] 取上述两种起源的最大值。

公式：dp[i][j] = Max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])

3) dp 数组初始化

依据 dp 数组的定义，背包容量为 0 时，最大价值永远为 0。dp[i][0] = 0

依据递推公式可知，i 取决于 i -1，所以要对 i = 0 时的状态做初始化。也就是只寄存物品 0 时，各个背包容量下的最大价值dp[0][j]

编码：

第一层循环物品，第二层循环背包容量

public static int packageOneOrZero(int[] weights, int[] values, int packageWeight) {// 定义 dp[i][j]示意 从 0~i 的物品中任意放入容量为 j 的背包，最大价值总和为 dp[i][j]
    int[][] dp = new int[values.length][packageWeight + 1];

    // dp[0][j]初始化
    for (int j = packageWeight; j >= weights[0]; j--) {dp[0][j] = dp[0][j - weights[0]] + values[0];
    }

    for (int i = 1; i < values.length; i++) {for (int j = 0; j <= packageWeight; j++) {if (j < weights[i]) {dp[i][j] = dp[i - 1][j];
    } else {dp[i][j] = Math.max(dp[i - 1][j - weights[i]] + values[i], dp[i - 1][j]);
    }
    }
    }
    return dp[values.length - 1][packageWeight];
    }

    public static void main(String[] args) {int[] weights = new int[] {1, 3, 4};
    int[] values = new int[] {15, 20, 30};

    System.out.println(packageOneOrZero(weights, values, 4));
}

简化思路：将 i - 1 和 i 进行合并，即应用一维数组进行运算

从新定义 dp 数组：dp[j]示意容量为 j 的背包，能够背的最大价值和为 dp[j]

递推公式：dp[j] = Max(dp[j], dp[j – weight[i]] + value[i])，实现了 dp[j]的复用

递推方向：为保障不反复取用物品，所以对于背包容量 j 的循环是倒序的

编码：

class Solution {public static int packageOneOrZero(int[] weights, int[] values, int packageWeight) {int[] dp = new int[packageWeight + 1];

        for (int i = 0; i < weights.length; i++) {for (int j = packageWeight; j >= weights[i]; j--) {dp[j] = Math.max(dp[j - weights[i]] + values[i], dp[j]);
            }
        }
        return dp[packageWeight];
    }

    public static void main(String[] args) {int[] weights = new int[] {1, 3, 4};
        int[] values = new int[] {15, 20, 30};

        System.out.println(packageOneOrZero(weights, values, 4));
    }
}
退出移动版