算法基础🔮 动态规划基础

数据结构与算法算法基础 #算法 #动态规划

2023-05-31 | 2024-04-17 | 2k | 8 分钟

什么是动态规划

动态规划 Dynamic Programming 简称 DP ，如果某一问题有很多重叠子问题，使用动态规划是最有效的；

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的；

动态规划的解题五步曲

确定 dp 数组以及下标的含义；

确定递推公式；

如何初始化 dp 数组；

确定遍历顺序；

举例推导 dp 数组；

0-1 背包理论基础

为什么称为 0-1 背包问题

由于每一个物品要么被选择放入背包，要么不放入背包，只有 不选（用 0 表示） 和 选（用 1 表示） 两种可能，因此称为 0-1 背包问题；
例如：有 N 个重量和价值分别为 W_i 和 V_i 的物品，从这些物品中挑选总重量不超过 W 的物品，每个物品只有一件，求所有挑选方案中价值总和的最大值；
```
# 输入
N = 4 
w = [4, 3, 1, 1]
v = [30, 20, 15, 20]
W = 5

# 输出
55
```
以表格的形式展示：

物品索引 i 0 1 2 3

重量 i 4 3 1 1

价值 i 30 20 15 20

物品索引 i	0	1	2	3
重量 i	4	3	1	1
价值 i	30	20	15	20

暴力方式

由于每一件物品都可以放进背包，也可以不放进背包，可以针对每一个物品 是否放入背包 进行搜索；这样 N 件物品就有 2^N 种选择，再对这 2^N 种选择方案进行遍历选出最大值，总的时间复杂度为：O(N * 2^N)；
下图是暴力解法的递归调用树形图：
可以发现，在第三层出现了数对 (3, 1) ，即：遇到了重复子问题；
暴力解法考虑了所有的情况，并且重复的子问题也进行了计算，时间复杂度高；可以采用 记忆化递归 的方式进行优化，执行相同参数的部分不会继续求解，由于参数 W 和 N 的组合一共有 NW 种，因此 记忆化递归 的时间复杂度为 O(NW)；

动态规划

确定 dp 数组以及下标的含义：dp[i][j] 的含义为从下标为 [0, i] 的物品里任意取，且重量总和不超过 j 时，背包能装下物品的 最大价值总和；
确定递推公式：可以有两个方向推出来 dp[i][j]
- 不放物品 i：dp[i - 1][j] 为背包容量为 j ，里面不放物品 i 的最大价值，此时 dp[i][j] 就是 dp[i - 1][j] （其实就是当物品 i 的重量大于背包 j 的重量时，物品 i 无法放进背包中，所以背包内的价值依然和前面相同）；
- 放物品 i：dp[i - 1][j - w[i]] 为背包容量为 j - w[i] 的时候不放物品 i 的最大价值，那么 dp[i - 1][j - w[i]] + value[i] 就是背包放物品 i 得到的最大价值；
- 所以递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + value[i])；
如何初始化 dp 数组：当背包空间为 0 时无法放入物品，则将二维数组第一列全部初始化成 0；
确定遍历顺序：
- 先遍历物品、先遍历背包重量都可以，但是先遍历物品更好理解；
- 此题先遍历物品，再遍历背包；
举例推导 dp 数组：

实现代码

function testWeightBagProblem(weight, value, size) {
    // 1. 定义 dp 数组
    const len = weight.length;
    const dp = Array(len).fill().map(() => Array(size + 1).fill(0));

    // 2. 初始化
    for (let j = weight[0]; j <= size; j++) {
        dp[0][j] = value[0];
    }

    // 3. weight 数组的长度 len 就是物品个数
    for (let i = 1; i < len; i++) { // 遍历物品
        for (let j = 0; j <= size; j++) { // 遍历背包容量
            if (j < weight[i]) {
                // 当前背包容量 < 物品重量，不放物品 i
                dp[i][j] = dp[i - 1][j];
            } else {
                // 放物品 i
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }

    console.table(dp);

    return dp[len - 1][size];
}

// 测试
console.log(testWeightBagProblem([4, 3, 1, 1], [30, 20, 15, 20], 5));
┌─────────┬───┬────┬────┬────┬────┬────┐
│ (index) │ 0 │ 1  │ 2  │ 3  │ 4  │ 5  │
├─────────┼───┼────┼────┼────┼────┼────┤
│    0    │ 0 │ 0  │ 0  │ 0  │ 30 │ 30 │
│    1    │ 0 │ 0  │ 0  │ 20 │ 30 │ 30 │
│    2    │ 0 │ 15 │ 15 │ 20 │ 35 │ 45 │
│    3    │ 0 │ 20 │ 35 │ 35 │ 40 │ 55 │
└─────────┴───┴────┴────┴────┴────┴────┘

动态规划（空间压缩）

对于背包问题其实状态都是可以压缩的：
- 其实可以把 dp[i - 1] 那一层拷贝到 dp[i] 上，可以转化成一个一维数组，只用 dp[j]；
- 这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层；
确定 dp 数组以及下标的含义：在一维 dp 数组中，dp[j] 表示容量为 j 的背包，所背的物品价值可以最大为 dp[j]；
确定一维 dp 数组的递推公式：dp[j] = max(dp[j], dp[j - w[i]] + value[i]) 相对于二维 dp 数组的写法，是把 dp[i][j] 中 i 的维度去掉了；
- 不放物品 i：dp[j] 相当于二维 dp 数组中的 dp[i-1][j]（其实就是当物品 i 的重量大于背包 j 的重量时，物品 i 无法放进背包中，所以背包内的价值依然和前面相同）；
- 放物品 i：dp[j - w[i]] 为背包容量为 j - w[i] 的时候不放物品 i 的最大价值，那么 dp[j - w[i]] + value[i] 就是背包放物品 i 得到的最大价值；
确定遍历顺序：
- 先遍历物品，再遍历背包；
- 状态值的更新只和它上边和左边的元素有关，把空间投影到一行后，状态转移（填表）的时候，从右边到左边更新状态值；

实现代码

function testWeightBagProblem(wight, value, size) {
    const dp = Array(size + 1).fill(0);

    for (let i = 1; i <= size; i++) {
        for (let j = size; j >= wight[i - 1]; j--) {
            dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);
        }
        console.log(dp);
    }

    return dp[size];
}

// 测试
console.log(testWeightBagProblem([4, 3, 1, 1], [30, 20, 15, 20], 5));
// [ 0,  0,  0,  0, 30, 30 ]
// [ 0,  0,  0, 20, 30, 30 ]
// [ 0, 15, 15, 20, 35, 45 ]
// [ 0, 20, 35, 35, 40, 55 ]

完全背包理论基础

什么是完全背包

在 0-1 背包问题 的基础上，去掉 每个物品只有一件 的限制，即总重量不超过背包承重，且每个物品有无数多件，问背包能装下物品的最大价值总和是多少；
例如：有 N 个重量和价值分别为 W_i 和 V_i 的物品，从这些物品中挑选总重量不超过 W 的物品，每种物品可以挑选 任意多件，求所有挑选方案中价值总和的最大值；
```
# 输入
N = 3 
w = [1, 3, 4]
v = [15, 20, 30]
W = 4

# 输出
60
```
以表格的形式展示：

物品索引 i 0 1 2

重量 i 1 3 4

价值 i 15 20 30

物品索引 i	0	1	2
重量 i	1	3	4
价值 i	15	20	30

动态规划（空间压缩）

确定 dp 数组以及下标的含义：与 0-1 背包 一致；
确定递推公式：与 0-1 背包 一致；
如何初始化 dp 数组：与 0-1 背包 一致；
确定遍历顺序：
- 0-1 背包 参考 上一行 的值，使用一维数组压缩空间的时候，倒序填表；
- 完全背包 参考 当前行 的值，使用一维数组压缩空间的时候，正序填表；
举例推导 dp 数组：

背包容量 j = 0 背包容量 j = 1 背包容量 j = 2 背包容量 j = 3 背包容量 j = 4

物品 i = 0 0 15 30 45 60

物品 i = 1 0 15 30 45 60

物品 i = 2 0 15 30 45 60

	背包容量 j = 1	背包容量 j = 2	背包容量 j = 3	背包容量 j = 4
物品 i = 0	15	30	45	60
物品 i = 1	15	30	45	60
物品 i = 2	15	30	45	`60`

实现代码

function testWeightBagProblem(weight, value, size) {
    let dp = new Array(size + 1).fill(0);

    for (let i = 0; i < weight.length; i++) {
        for (let j = weight[i]; j <= size; j++) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    return dp[size];
}