背包问题学习笔记-混合背包问题

题意描述：

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；每种体积是 vi，价值是 wi。

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

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

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

si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；

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

数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
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

示例：

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

8

---

解题思路：
Alice: 笑死🤣，这题可以直接改一下输入，改成多重背包就可以了
Bob: 对，01背包的物品数量就是 1，数量 1 也是多重背包的一种。完全背包的话，背包体积是有限的，能装进去的物品数量也是有限的，直接算一下，然后上取整就得了。其他代码不用改，直接用单调队列优化的肯定能过。

---

代码：

转换成多重背包 + 单调队列求解

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,
            volumAndWeightAndCount: list.slice(countAndVolumIndex + 1, countAndVolumIndex + 1 + count).map(item => {
                const [v, w, s] = item;
                let normalizedS = s;
                if(s === -1) {
                    normalizedS = 1;
                }
                if(s === 0) {
                    normalizedS = Math.ceil(volum / v);
                }
                return [v, w, normalizedS];
            }),
        });
        countAndVolumIndex += count + 1;
    }
    
    data.forEach(item => {
        if(solve && item && item.count && item.volum) {
            solve(item.count, item.volum, item.volumAndWeightAndCount);
        }
    });
}


const solve = (count, maxVolum, volumAndWeightAndCount) => {
    // 单调队列优化方法
    const dp = new Array(maxVolum + 10).fill(0);
    // 对于每种物品 
    for (let i=0; i<count; ++i) {
        // 状态压缩
        const lastRowDp = [...dp];
        // 取出第 i 种物品的体积，价值，数量
        const [vi, wi, si] = volumAndWeightAndCount[i];
        // 对于每种可能剩余的体积，0,1,2, ... vi-1 
        for (let r=0; r<vi; ++r) {
            // 单调队列求解每种可能的最大值，滑动窗口大小是，math.min (si, maxVolum / vi) 下取整
            // 0 + 0v, 0 + 1v, 0 + 2v ... 0 + kv 的数组中滑动，每次一步
            // 最大价值对应的体积的单调队列，双端队列，queue[0] 是合法的最大价值对应的体积
            const queue = [];
            for(let j=r; j<=maxVolum; j+=vi) {
               // 维护队首
               // i 物品的体积超了
               while(queue.length && j-queue[0] > vi*si) {
                   queue.shift();
               }
               // 维护队尾
               while(queue.length && lastRowDp[queue[queue.length-1]] + (j - queue[queue.length-1]) /vi * wi <= lastRowDp[j]) {
                   queue.pop();
               }
               // 入队
               queue.push(j);
               // 更新 dp
               dp[j] = lastRowDp[queue[0]] + (j-queue[0]) / vi * wi;
            }
        }
    }

    
    console.log(dp[maxVolum]);
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

参考：

• 题目链接