01背包问题的一维数组表示形式

这篇文章，我们来谈一谈什么是01背包问题？

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

这个问题，相信接触过的都会想到用动态规划来解决，却对本题的暴力解法没有头绪，下面介绍解决01背包问题的三种解法。

1. 暴力回溯法
2. 二维数组-动态规划
3. 一维数组-动态规划

暴力回溯法：

递归遍历整个物品数组，递归出口就是背包容量装不下物品，求最大价值。时间复杂度为2^n

代码算法如下：

function testWeightBagProblem(weight, value, size) {
    let maxValue = 0;
    const backTracking = (currentSize, currentValue, start) => {
        if (currentSize > size) return;
        if (currentSize <= size) maxValue = Math.max(maxValue, currentValue);
        for (let i = start; i < weight.length; i++) {
            currentSize += weight[i];
            currentValue += value[i];
            backTracking(currentSize, currentValue, i + 1);
            currentSize -= weight[i];
            currentValue -= value[i];
        }
    };
    backTracking(0, 0, 0);
    console.log(maxValue);
}

testWeightBagProblem([1, 3, 4], [15, 20, 30], 4);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路：枚举一下每种情况，然后进行暴力搜索，每种结果都会在递归的开始阶段来进行判断。

动态规划二维数组的表示方式：

相信做01背包问题，大家最先想到的就是二维dp数组，然后利用动态规划。做动态规划我们要思考下面五步

1.确认dp数组的含义以及下标的含义
2.确认递推公式
3.dp数组的初始化
4.dp数组的遍历顺序
5.打印dp数组进行调试
1
2
3
4
5

1.定义一个dp数组 dp[i][j]其中数组下标i表示从[0,i]选择的物品，下标j表示背包的容量为j dp表示的是最大价值

2.dp[i][j]有两种情况，下标为i的物品没有选择 dp[i][j]=dp[i-1][j] 下标为i的物品选择了dp[i][j]==dp[i-1][j-weight[i]]+value[i]。既然是最大价值，那么就取两者中大的那一个。

3.初始化。 j为0的时候，dp[i][j]==0 i为0的时候，dp[i][j]就看能不能放下第一个物品的重量了。

4.从前往后遍历

最后代码如下：

/**
 *
 * @param {Array} weight
 * @param {Array} value
 * @param {Number} size
 */
function testWeightBagProblem(weight, value, size) {
    // dp[i][j]表示[0,i] 背包重量为j的物品的最大价值
    let dp = new Array(weight.length)
        .fill(0)
        .map(() => new Array(size + 1).fill(0));
    for (let i = 0; i < weight.length; i++) {
        dp[i][0] = 0;
    }
    for (let i = 0; i <= size; i++) {
        if (i >= weight[0]) {
            dp[0][i] = value[0];
        }
    }
    for (let i = 1; i < weight.length; i++) {
        for (let j = 1; j <= size; j++) {
            if (j - weight[i] >= 0) {
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    dp[i - 1][j - weight[i]] + value[i]
                );
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[weight.length - 1][size];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

一维数组：

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight*[i]] + value*[i]);观看这个结构，我们可以算dp[i][j]总要依赖上次的dp[i-1]的状态。我们其实可以用一维数组来模拟这个过程。

1.设dp[j]表示背包容量为j的最大价值

2.dp[j] = Math.max(dp[j],max[j-weight[i]]+value[i])

3.dp[j]初始化 dp[0]=0 表示背包容量为0的最大价值为0

4.遍历顺序：这一步需要注意，因为我们要依赖于上一次的状态，因此我们需要从后往前遍历，不然我们就会造成重复累加。

/**
 *
 * @param {Array} weight
 * @param {Array} value
 * @param {Number} size
 */
function testWeightBagProblem(weight, value, size) {
    let dp = new Array(size + 1).fill(0);
    for (i = 0; i < weight.length; i++) {
        for (let j = size; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[size];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

读者这里注意，从前遍历和从后遍历的区别。

小结：

01背包问题是背包问题的一个经典类型。主要分为暴力和动态规划两种解法，希望本篇文章让读者对01背包问题有一定的理解。🎉🎉🎉🎉🎉