算法入门第一篇—01背包

大熙哥 2021年08月13日 110次浏览

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

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)