背包：0-1 背包问题

#算法/动态规划

目录

题目

image.png|504

image.png|464

举例说明：

  • N = 3 表示可选择的物品有 三件
  • W = 4 表示包能装 4kg 的物品
  • wt = [2, 1, 3] 表示每件物品的重量
  • val = [4, 2, 3] 表示每件物品的价值

那么最大价值是：选择前两个物品，因为最大价值是 6

明确 状态 与 选择

状态， 即什么在变化？，有两个**状态

  • 包还能装多少？
  • 还可选择的物品

选择，对于一个物品，你装还是不装？

  • 装
  • 不装

明确 dp数组 的定义

  • 状态有多少个，决定 dp数组 是 几维数组
  • dp[i][w] 的定义如下：
    • 对于前 i 个物品，当前背包的 剩余 容量 为 w， 这种情况下可以装的最大价值是 dp[i][w]
    • dp[3][5] = 6，其含义为：
      • 对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包剩余容量为 5 时，最多可以装下的价值为 6
  • 所以
    • base case：
      • dp[i][0] = 0 ， dp[0][w] = 0
      • 根据一定规则（状态转移方程）
    • 推导出 => dp[N][W] 即是所要求的值

根据动态规划框架 写出 此题的伪码

// base case：
dp[0][...] = base case

// 根据状态的个数，嵌套遍历：
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

// 初始化 二维 dp 数组
dp[N+1][W+1]

// base case : 无论哪个指标为 0，dp 数组都为 0
dp[0][..] = 0
dp[..][0] = 0

// 根据状态，嵌套遍历，下标从 1 开始，=>  推导出 dp[N][W]
for i in [1..N]:
    for w in [1..W]:
        dp[i][w] = max(
            把物品 i 装进背包,
            不把物品 i 装进背包
        )

return dp[N][W]

对于 dp[i][w] ，来自于两个选择

  • 选择一： 第 i 物品不装入
    • dp[i][w] = 剩余重量为 w 的包选择前 i-1 个物品的价值，即dp[i-1][w]
  • 选择二： 第 i 个物品装入
    • dp[i][w] =
      • 在剩余重量为 w - wt[i-1]限制下， 选择装前 i-1 个物品的价值 + 第 i 个物品的价值 val[i] ，即
      • dp[i-1][w - wt[i-1]] + val[i-1]

数组索引问题导致的误解：

  • 因为数组索引问题： val[i-1] 和 wt[i-1] 表示第 i 个物品的价值和重量

所以对于第 i 个物品，我们选择装入，也就是说前i-1 个物品，只能装到 剩余重量 为 w - wt[i-1] ，即 dp[i-1][w-[w-1]

最终代码

/**
* @description 0/1 Knapsack Problem
* */
function fn(N, W, wt, val) {
    // ::::1、初始化dp数组
    const dp = [];
    for (let i = 0; i <= N; i++) {
        dp[i] = [];
        for (let j = 0; j <= W; j++) {
            dp[i][j] = 0;
        }
    }
    // ::::2、base case
    for (let i = 0; i <= N; i++) {
        dp[i][0] = 0;
    }
    for (let i = 0; i <= W; i++) {
        dp[0][i] = 0;
    }
    // ::::3、动态规划框架，根据状态个数，决定嵌套层数
    for (let i = 1; i <= N; i++) {
        for (let w = 1; w <= W; w++) {
            // 剩余容量已经小于 0 了，只能选择不装入
            if (w - wt[i - 1] < 0) {
                dp[i][w] = dp[i - 1][w];
            } else {
                // 选择：装入 或者 不装入
                dp[i][w] = Math.max(
                    // 不装入
                    dp[i - 1][w],
                    // 装入
                    dp[i - 1][w - wt[i - 1]] + val[i - 1]
                )
            }
        }
    }
    console.log(dp)
    return dp[N][W];
}

// const N = 3, W = 4,
//     wt = [2, 1, 3],
//     val = [4, 2, 3];
const N = 5, W = 50,
    wt = [10, 20, 30, 40, 50],
    val = [50, 120, 150, 210, 240];

console.log(fn(N, W, wt, val));

错误记录

image.png|552

  • 需要 从 1 开始遍历
  • 注意两个变量 w 和 wt 别搞混了