背包问题学习笔记-01背包

背景

背包问题是动态规划问题中的一个大类，学习背包问题对于掌握动态规划十分重要。背包问题也很容易成为程序员算法面试中的一个槛，但其实背包问题已经被研究，讲解的比较成熟了，在这些丰富的讲解资料的基础之上，大家理解背包问题的难度也被大大减弱了。

本篇笔记主要参考了 AcWing 上的题目列表以及讲解视频，原因有二：1）上面截图中相关的问题都是免费的，不需要会员。2）AcWing 作者的讲解较为细致，适合新手学习。

题意描述：

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i  件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000

0<vi,wi≤1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

示例：

4 5
1 2
2 4
3 4
4 5

8

---

解题思路：

Alice: 01 背包有思路吗 ？
Bob: 我记得这个是动态规划，好像还是二维动态规划 ？
Alice: 状态转移方程能找到吗 ？
Bob: 找状态转移方程之前得先明确要记录的状态是啥，dp[i][j] 是什么意思吧 ？
Alice: 说的对，dp[i][j] 的值一般的话，应该就是要求解的值吧，就是最大价值。
Bob: 那 i 和 j 呢 ？还剩下的变量是什么 ？物品的体积，物品的 ID ? 背包的体积 ？
Alice: 背包的体积是个常量，背包中可用的体积在状态转移的时候是个变量。
Bob: 那让 dp[i][j] 是前 i 个物品，在背包剩余体积是 j 的状态下的最大价值 ？
Alice: 不应该绕一道，让 dp[i][j] 是前 i 个物品在消耗了 j 的体积下的最大价值就好了。这样的话， dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[j]] + w[j] ) ？
Bob: 我想想 🤔️，第 i 个物品不装入背包的时候，最大价值就是前 i-1 个物品在 j 的体积下的最大价值，就是 dp[ i - 1 ][j] 。第 i 个物品装入背包的时候，装的下吗 ？如果要装的下的话，应该是 dp[i-1][j - v[j]] + w[j]， 也就是说前 i-1 个物品最多消耗 j-v[j] 的空间，这样才放得下，然后加上第 j 个物品的价值 w[j] 就可以了。
Alice: 对，应该没问题。
Bob: 具体的求解过程呢 ？初始化一个二维数组，一维是物体数量，二维是背包体积，初始化都是 0，然后从上到下，从左到右按照上面的 递推公式求解二维数据，最后整个数组的最大值就是答案 ？
Alice: 我去试试 💃 … 果然过了。
Bob: 计算的过程感觉还是要注意一下，初始化的时候还要先求解第一行的。

---

Alice: 听说还有什么状态压缩 ？
Bob: 减少二维数组消耗的内存 ？把 n*m 的数据改成 2 * m 的，因为每次计算只有两行之间的递推关系。
Alice：有点麻烦，需要来回的覆写数组。
Bob: 难道是能改成一维的动态规划 !!
Alice: 应该是吧，dp[i][j] 表示的是前 i 个物品消耗体积小于等于 j 时的最大价值，改成一维的话，i 和 j 应该保留哪个呢 ？
Bob: 哪个能完成状态转移就保留哪个吧，值肯定还是最大价值。保留体积 j 的话，dp[j] = max(dp[j], dp[j-v[i]] + w[i]) ，是这样的吗 ？
Alice: 怎么还有 i 呢 ？
Bob: 当然还有 i, 状态转移还是第 i 个物品要不要装进去。双循环是不变的，只是优化是有的二维数组的空间。
Alice：你去试试 ？
Bob: 有个麻烦的点，很难理解。计算体积的时候要反向计算，因为 dp[j] 依赖于 dp[j-ivolum]，而这两个东西是在一个一维数组里面不断更新的，所要要先更新 dp[j] 再更新 dp[j-ivolum]，不然就算不对了。
Alice：确实 🤔️

---

Alice: 还有一件事，我听嗦状态压缩之后根本不用求最大值，dp[maxVolumn] 就是最大值，是真的吗 ？
Bob: 这个和你初始化的方式有关系，如果 dp 全都初始化成 0，那 dp[maxVolumn] 就是最大值，否则不一定。
Alice: 这么神奇的吗 ？
Bob: 最的价值不一定把背包填满了，假设最大价值时消耗的空间是 k，且 k < maxVolumn 想一下这个时候的状态转移。
Alice: 如果不把 dp 都初始化为 0，那应该怎么初始化，dp[0] = 0，其他空间初始化成负无穷 ？
Bob: 对，这样在算的时候 dp[j] = max(dp[j], dp[j-v[i]] + w[i]) ，如果 j-v[i] 不是一个有效的填充体积，那 dp[j] 就还是负无穷，只有有效的填充体积才能有价值。这个时候是需要求最大值的。
Alice: 我去试试
Bob: 给你个测试用例

5 4
2 2
2 4
3 4
4 5
3 7
1
2
3
4
5
6

dp 算完应该是这样的 [ 0, -Infinity, 4, 7, 6 ]

---

代码：

二维动态规划 + js

const fs = require('fs');
let buffer = '';

process.stdin.on('readable', () => {
    const chunk = process.stdin.read();
    if (chunk) {
        buffer += chunk.toString()
    }
});

// 输入的字符串转换为数字
const convert = (inputString) => {
    const list = [];
    inputString.split('\n').forEach((line) => {
        const tokens = line.split(' ');
        list.push(tokens.map(num => parseInt(num, 10)));
    });
    return list;
}

// 批量调用
const batchCall = (list, solve) => {
    // 划分数据
    const data = [];
    let countAndVolumIndex = 0;
    while(countAndVolumIndex < list.length) {
        const [count, volum] = list[countAndVolumIndex];
        data.push({
            volum: volum,
            count: count,
            volumAndWeight: list.slice(countAndVolumIndex + 1, countAndVolumIndex + 1 + count)
        });
        countAndVolumIndex += count + 1;
    }
    
    data.forEach(item => {
        // 防止空行或者无效数据
        if(solve && item && item.count && item.volum) {
            solve(item.count, item.volum, item.volumAndWeight);
        }
    });
}


const solve = (count, maxVolum, volumAndWeight) => {
    const dp = [];
    for(let i=0; i<=count; ++i) {
        dp.push(new Array(maxVolum + 1).fill(0));
    }
    
    // 初始化第一行
    const [firstThingVolum, firstThingWeight] = volumAndWeight[0];
    for(let j=0; j<=maxVolum; ++j) {
        dp[0][j] = j >= firstThingVolum ? firstThingWeight : 0;
    }
    
    let result = 0;
    for(let i=1; i<count; ++i){
        for(let j=0; j<=maxVolum; ++j) {
            // 第 i 个物品的体积和价值
            const [ivolum, iweight] = volumAndWeight[i];
            dp[i][j] = dp[i-1][j];
            if (j >= ivolum) {
                dp[i][j] = Math.max(
                    dp[i-1][j],
                    dp[i-1][j-ivolum] + iweight
                )
            }
            result = Math.max(result, dp[i][j]);
        }
    }
    console.log(result);
}

process.stdin.on('end', function() {
    batchCall(convert(buffer), solve)
});
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

状态压缩 + js

const fs = require('fs');
let buffer = '';

process.stdin.on('readable', () => {
    const chunk = process.stdin.read();
    if (chunk) {
        buffer += chunk.toString()
    }
});

// 输入的字符串转换为数字
const convert = (inputString) => {
    const list = [];
    inputString.split('\n').forEach((line) => {
        const tokens = line.split(' ');
        list.push(tokens.map(num => parseInt(num, 10)));
    });
    return list;
}

// 批量调用
const batchCall = (list, solve) => {
    // 划分数据
    const data = [];
    let countAndVolumIndex = 0;
    while(countAndVolumIndex < list.length) {
        const [count, volum] = list[countAndVolumIndex];
        data.push({
            volum: volum,
            count: count,
            volumAndWeight: list.slice(countAndVolumIndex + 1, countAndVolumIndex + 1 + count)
        });
        countAndVolumIndex += count + 1;
    }
    
    data.forEach(item => {
        if(solve && item && item.count && item.volum) {
            solve(item.count, item.volum, item.volumAndWeight);
        }
    });
}


const solve = (count, maxVolum, volumAndWeight) => {
    const dp = new Array(maxVolum + 1).fill(0);
    
    let result = 0;
    for(let i=0; i<count; ++i){
        // 为何这里是从大到小反向计算呢 ？
        // 从第二个物品开始思考，第一个物品计算完了的时候，dp[j] 就是 dp[i-1][j], 
        // 现在我们要更新 dp[j] 的数据，从右往左更新，是因为右依赖左，
        // dp[j] 的计算要依赖 dp[j-ivolum],所以要保证计算 dp[j] 的时候，
        // dp[j-ivolum] 还是 i-1 的时候的值。
        for(let j=maxVolum; j>=0; --j) {
            // 第 i 个物品的体积和价值
            const [ivolum, iweight] = volumAndWeight[i];
            if (j >= ivolum) {
                dp[j] = Math.max(
                    dp[j],
                    dp[j-ivolum] + iweight
                )
            }
            
            result = Math.max(result, dp[j]);
        }
    }

    console.log(result);
}

process.stdin.on('end', function() {
    batchCall(convert(buffer), solve)
});
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

状态压缩 + 是否精确求解 + js

dp[j] 为体积恰好等于 j 时的最大价值

const solve = (count, maxVolum, volumAndWeight) => {
    const dp = new Array(maxVolum + 1).fill(-1 * Infinity);
    dp[0] = 0;
    
    for(let i=0; i<count; ++i){
        for(let j=maxVolum; j>=0; --j) {
            // 第 i 个物品的体积和价值
            const [ivolum, iweight] = volumAndWeight[i];
            if (j >= ivolum) {
                dp[j] = Math.max(
                    dp[j],
                    dp[j-ivolum] + iweight
                )
            }
        }
    }
    console.log(Math.max(...dp));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

dp[j] 为体积 <= j 时的最大价值

const solve = (count, maxVolum, volumAndWeight) => {
    const dp = new Array(maxVolum + 1).fill(0);
    
    for(let i=0; i<count; ++i){
        for(let j=maxVolum; j>=0; --j) {
            // 第 i 个物品的体积和价值
            const [ivolum, iweight] = volumAndWeight[i];
            if (j >= ivolum) {
                dp[j] = Math.max(
                    dp[j],
                    dp[j-ivolum] + iweight
                )
            }
        }
    }

    console.log(dp[maxVolum]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

参考：

• 题目链接
• 讲解