Version: Next

0 - 1 背包问题

贪心法

有n件物品和一个最大承重为W的背包，每件物品的重量是W_i，价值是V_i

  • 问：在保证总重量不超过W的前提下，将哪几件物品装入背包，可以是背包的总价值最大?
  • 每种物品只有 1 件，即每种物品只能选择 0 件或者 1 件，故称为 0-1 背包问题

如果采用贪心算法，有 3 个方案

  1. 价值主导：优先选择最值钱的放进背包
  2. 重量主导：优先选择重量最轻的物品放进背包
  3. 价值密度主导：优先选择 density = value / weight 最高的物品放入背包
  • 假设背包最大承重为150，现有7个物品如表格所示
编号重量价值价值密度
135100.29
230401.33
360300.5
450501.0
540350.88
610404.0
725301.2
  • 价值主导法：依次放入 4、2、6、5，总重量 130 ，总价值 165
  • 重量主导法：依次放入6、7、2、1、5，总重量 140 ，总价值 155
  • 价值密度主导法：依次放入6、2、7、4、1，总重量为 150 ，总价值 170
背包物品实体类
package com.bsx.algorithm.pojo;
import lombok.Data;
import lombok.NoArgsConstructor;
/**
* 物品
*/
@Data
@NoArgsConstructor
public class Item {
private int weight;
private int value;
private double valueDensity;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
this.valueDensity = value * 1.0 / weight;
}
@Override
public String toString() {
return "Item{" +
"重量=" + weight +
", 价值=" + value +
", 价值密度=" + valueDensity +
'}';
}
}
贪心法解01背包问题
/**
* 01背包问题，贪心法 ，接收不同的比较器来实现不同的选取规则
* 价值主导
* 重量主导
* 价值密度主导
*/
public class ZeroOneBagGreedy {
public static void main(String[] args) {
Item[] items = new Item[]{
new Item(35, 10),
new Item(30, 40),
new Item(60, 30),
new Item(50, 50),
new Item(40, 35),
new Item(10, 40),
new Item(25, 30)
};
// 按价格，从高到低排序
Comparator<Item> valueComparator = (i1, i2) -> i2.getValue() - i1.getValue();
// 按重量，从小到大排序
Comparator<Item> weightComparator = (i1, i2) -> i1.getWeight() - i2.getWeight();
// 按价格密度，从高到低排序
Comparator<Item> valueDensityComparator = (i1, i2) -> Double.compare(i2.getValueDensity(), i1.getValueDensity());
System.out.println("价值主导");
solve(items, 150, valueComparator);
System.out.println("重量主导");
solve(items, 150, weightComparator);
System.out.println("价值密度主导");
solve(items, 150, valueDensityComparator);
}
/**
* @param items 物品数组
* @param maxWeight 背包的最大承重
* @param comparator 外部传入的比较规则，决定价值主导、重量主导、价值密度主导
*/
private static void solve(Item[] items, int maxWeight, Comparator<Item> comparator) {
System.out.println("背包默认承重量为 [" + maxWeight + "]");
int remainWeight = maxWeight; // 剩余背包承重
int resultValue = 0; // 最终价值
// 按照 "规则" 排序
Arrays.sort(items, comparator);
for (Item item : items) {
int currentItemWeight = item.getWeight();
if (remainWeight >= currentItemWeight) {
remainWeight -= item.getWeight();
resultValue += item.getValue();
System.out.println("拿了重量为 [" + item.getWeight()
+ "], 价值 [" + item.getValue() + "] 的物品 | 当前共装了重 ["
+ (maxWeight - remainWeight) + "] 的物品，背包剩余承重为 ["
+ remainWeight + "]，总价值为 [" + resultValue + "] ");
}
}
System.out.println("拿不下了 \n");
}
}
运行结果
价值主导
背包默认承重量为 [150]
拿了重量为 [50], 价值 [50] 的物品 | 当前共装了重 [50] 的物品，背包剩余承重为 [100]，总价值为 [50]
拿了重量为 [30], 价值 [40] 的物品 | 当前共装了重 [80] 的物品，背包剩余承重为 [70]，总价值为 [90]
拿了重量为 [10], 价值 [40] 的物品 | 当前共装了重 [90] 的物品，背包剩余承重为 [60]，总价值为 [130]
拿了重量为 [40], 价值 [35] 的物品 | 当前共装了重 [130] 的物品，背包剩余承重为 [20]，总价值为 [165]
拿不下了
重量主导
背包默认承重量为 [150]
拿了重量为 [10], 价值 [40] 的物品 | 当前共装了重 [10] 的物品，背包剩余承重为 [140]，总价值为 [40]
拿了重量为 [25], 价值 [30] 的物品 | 当前共装了重 [35] 的物品，背包剩余承重为 [115]，总价值为 [70]
拿了重量为 [30], 价值 [40] 的物品 | 当前共装了重 [65] 的物品，背包剩余承重为 [85]，总价值为 [110]
拿了重量为 [35], 价值 [10] 的物品 | 当前共装了重 [100] 的物品，背包剩余承重为 [50]，总价值为 [120]
拿了重量为 [40], 价值 [35] 的物品 | 当前共装了重 [140] 的物品，背包剩余承重为 [10]，总价值为 [155]
拿不下了
价值密度主导
背包默认承重量为 [150]
拿了重量为 [10], 价值 [40] 的物品 | 当前共装了重 [10] 的物品，背包剩余承重为 [140]，总价值为 [40]
拿了重量为 [30], 价值 [40] 的物品 | 当前共装了重 [40] 的物品，背包剩余承重为 [110]，总价值为 [80]
拿了重量为 [25], 价值 [30] 的物品 | 当前共装了重 [65] 的物品，背包剩余承重为 [85]，总价值为 [110]
拿了重量为 [50], 价值 [50] 的物品 | 当前共装了重 [115] 的物品，背包剩余承重为 [35]，总价值为 [160]
拿了重量为 [35], 价值 [10] 的物品 | 当前共装了重 [150] 的物品，背包剩余承重为 [0]，总价值为 [170]
拿不下了

动态规划法

  1. 定义状态：假设 values 是价值数组， weight 是重量数组
    • 编号为 k 的物品，价值是 values[k] ，重量是 weights[k] ， k ∈ [0, n)
    • 假设 dp(i, j) 是最大承重为 j， 有前 i 件物品可选时的最大总价值， i ∈ [0, n], j ∈ [0, w]
      • dp(3, 7) 表示最大承重为 7，有前 3 件物品可选时的最大价值
    • 所求解即为 dp(n, capacity)
  2. 初始条件
    • dp(i, 0) = dp(0, j) = 0
  3. 状态转移方程
    • 如果最后一件物品不选，那么 dp(i, j) = dp(i-1, j)
    • 如果最后一件物品被选了（第 i 件物品，当前它的下标是 i - 1），则最大承重减去它的重量，对应dp值加上它的价值，即 dp(i, j) = dp(i-1, j-weight[i-1]) + values[i-1]
    • 决策：决定到底拿了好还是不拿好： 在上述两种情况的 dp 值中，选二者较大的那个，即 dp(i, j) = max { dp(i-1, j), dp(i-1, j-weight[i-1]) + values[i-1] }
    • 当然，需要考虑剩余承重，
      • 确保 j >= weights[i - 1] 才能拿，则 dp(i, j) = max { dp(i-1, j), dp(i-1, j-weight[i - 1]) + values[i - 1] }
      • 否则 j < weights[i - 1]，表示不能再拿，那么 dp(i, j) = dp(i-1, j)
/**
* 动态规划——01背包问题
*/
public class ZeroOneBagDp {
/**
* @param values 价值数组
* @param weights 重量数组
* @param capacity 背包容量
* @return
*/
private static int maxValue(int[] values, int[] weights, int capacity) {
if (values == null || values.length == 0) return 0;
if (weights == null || weights.length == 0) return 0;
if (values.length != weights.length || capacity <= 0) return 0;
int[][] dp = new int[values.length + 1][capacity + 1];
for (int i = 1; i <= values.length; i++) {
for (int j = 1; j <= capacity; j++) {
if (j < weights[i - 1]) // 表示不能再拿了
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(
dp[i - 1][j],
dp[i - 1][j - weights[i - 1]] + values[i - 1]
);
}
}
return dp[values.length][capacity];
}
public static void main(String[] args) {
int[] values = {6, 3, 5, 4, 6};
int[] weights = {2, 2, 6, 5, 4};
int capacity = 10;
int res = maxValue(values, weights, capacity);
System.out.println("res = " + res);
}
}

滚动数组优化空间复杂度

  • 观察上述 dp 数组中的 i，发现在状态转移方程中，只涉及 i 与 i - 1，根据无后效性，其实用一个数组就行了
  • 那么整个 i 这个维度可以被移除，只剩下 j 就行了，使用一个一维数组
  • 由于 dp[j] 依赖于 dp[j - w[i]] ，j - w[i] < j，也就是在一个一维数组中，计算右侧的j需要用到左侧的 j 上的上一轮数据，那么从左往右递推就会令新的值覆盖旧的值，因此递推方向应当是 从右向左
  • 写出滚动数组下的状态转移方程： dp[j - weight[i]] + values[i - 1] 与 dp[j] 二者的最大值
    • 需要限定 j >= w[i] 防止下标越界
    • 递推方向为 i 从左往右， j 从右向左
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}