发表于 | 分类于 | 0 | 阅读次数 653

后知后觉才知道算法的重要性，从今天开始更新点算法类的文章。

image.png

背包分析

01背包是什么？

01背包有N种物品，每种物品只有一个。

完全背包是什么？

完全背包有N种物品，每种物品有无限个。

二维dp数组分析

名称重量价值
物品0115
物品1320
物品2430

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

其中一种写法是使用二维数组，dp[i][j]
表示从下标【0-i】的物品里面任意取，放进容量为j的背包，价值总和最大为多少。

tips：跳出思维误区，在这里我们总以为这个i是一个固定整数，实际上在我们的思维应该是这么想的，他代表一个范围表示【0-i】，假设现在i是5，那么他表示的是一个范围 【0-4】任意取放进容量为j的背包价值总和最大为多少。

二维数组如图所示：

名称\容量01234
物品0
物品1
物品2

2. 确定递推公式

目标是推出dp[i][j]

首先往回走看看

dp[i - 1][j]

就是不放物品i的最大价值。

dp[i - 1][j - weight[i]]

为背景容量减去i的重量，不放物品i的最大价值。

dp[i - 1][j - weight[i]] + value[i]

背包放下物品i得到的最大价值

最后递推公式为

dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i] )

3. dp数组初始化

首先从背包容量开始初始化，背包容量为0的话，背包最大价值一定为0。

名称\容量01234
物品00
物品10
物品20

对递推公式分析，得出i是由i-1推导过来的，那么i为0时一定要初始化。

名称\容量01234
物品0015151515
物品10
物品20

其他非0下标怎么办呢？
其实我观察发现推导dp[i][j]是由上面或左上角进行推导出来的，所以初始化非0下标的可以是任意，甚至是不定义。

注意！如果题目给的价值有负数，非0下标就要初始化为负无穷，原因很简单，我们取的是Max最大值，如果题目有负数，那么最大价值很有可能会是负数，此时 0 与 负数 相比就会取0，造成结果的不正确。

4. 确定遍历顺序

通过观看下列的二维数组，可以发现两个遍历的维度：物品与背包重量。

名称\容量01234
物品0015151515
物品10
物品20

先遍历 物品还是先遍历背包重量呢？都可以，但是先遍历物品更好理解。
为什么？观察发现推导dp[i][j]是由上面或左上角进行推导出来的。

5. 举例推导dp数组

做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！

例题分析

1. 斐波那契数

  1. 确定dp数组以及下标的含义
    dp[i]的定义为：第i个数的斐波那契数值是dp[i]
  2. 确定递推公式
dp[i] = dp[i - 1] + dp[i - 2]
  1. dp数组如何初始化
dp[0] = 0
dp[1] = 1
  1. 确定遍历顺序
    从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的。
  2. 举例推导dp数组
    按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
    0 1 1 2 3 5 8 13 21 34 55

代码：

/**
 * for循环快，好像没缺点，还可以获得数组
 * @date 2021-07-18
 * @param {Number} n
 * @returns {Array}
 */
function fibonacci_for(n) {
    let data = [1,1]
    for(let i = 2; i < n; i++) {
        sum = data[i-2] + data[i-1]
        data[i] = sum
    }
    return data
}

2. 01背包

物品价值和重量如图所示：

名称重量价值
物品0115
物品1320
物品2430

二维数组dp如图所示：

名称\容量01234
物品0015151515
物品10
物品20

推导过程在上方已经进行了推导。因此此处直接给出代码。
代码：

let weight = [1, 3, 4]   //物品重量
let value = [15, 20, 30] //物品价值
let bagWeight = 4 //背包容量
let n = 3 //物品总数

//dp
let dp = new Array(n).fill(0).map(v => new Array(bagWeight).fill(0))
console.log(dp)
//初始化dp
for (let i = 0; i < bagWeight; i++) {
    dp[0][i] = value[0]
}
console.log(dp)
for (let i = 1; i < weight.length; i++) { //遍历物品
    for (let j = 0; j < bagWeight; j++) { //遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
    }
}
console.log(dp)
0%