背包问题学习笔记-分组背包

题意描述：

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

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

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

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

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例：

3 5
2
1 2
2 4
1
3 4
1
4 5

8

---

解题思路：
Alice:这题有什么思路吗 ？感觉是套了两层的背包问题 ？
Bob: 这题的数据范围倒是挺小，都是 100 以内。
Alice: 假如是两层背包套在一起，把每组看成一个背包，如何求每组对应的物品的价值和体积呢 ？
Bob: 这个能算出来吗 ？把每组看成一个背包，组内又是一个 01 背包问题 ？
Alice: 能转成其他的背包问题吗 ？每组内有若干个物品，组内是 01 背包，我好像明白了，想一下多重背包的求解思路。
Bob: 哦豁，还真是，每个物品有 n 个，每组物品有 k 个只能选一个的物品，对第 i 组物品，直接考虑存在的多种选择就行了。
Alice: dp[j] = max ( dp[j], dp[j-v1] + w1, dp[j-v2] + w2 ...)，果然是转成了多重背包的做法。
Bob：代码写起来还不复杂，输入的数据转换逻辑给我写的有点难受了。

---

代码：

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)).filter(item => !item || !item.length));
    });
    return list;
}

// 批量调用
const batchCall = (list, solve) => {
    // 划分数据
    const data = [];
    let countAndVolumIndex = 0;
    while(countAndVolumIndex < list.length) {
        const [count, volum] = list[countAndVolumIndex];
        
        const volumAndValueByGroup = [];
        let groupNumIndex = countAndVolumIndex + 1;
        let groupCount = 0;
        // 读取每个分组的数据
        while(groupCount < count) {
            const left = groupNumIndex + 1;
            const right = groupNumIndex + 1 + list[groupNumIndex][0];
            volumAndValueByGroup.push(list.slice(left, right));
            groupNumIndex = right;
            groupCount += 1;
        }
        
        data.push({
            volum: volum,
            count: count,
            volumAndValueByGroup,
        });
        
        countAndVolumIndex = groupNumIndex;
    }
    
    data.forEach(item => {
        if(solve && item && item.count && item.volum) {
            solve(item.count, item.volum, item.volumAndValueByGroup);
        }
    });
}


const solve = (count, maxVolum, volumAndValueByGroup) => {
    const dp = new Array(maxVolum + 1).fill(0);
    
    for(let i=0; i<count; ++i){
        // 第 i 组物品的体积和价值
        const volumAndValue = volumAndValueByGroup[i];
        for(let j=maxVolum; j>=0; --j) {
            // 第 i 组物品什么也不选
            const candiantes = [dp[j]];
            // 选一个
            for(let k=0; k<volumAndValue.length; ++k) {
                const [kvolumn, kvalue] = volumAndValue[k];
                j - kvolumn >= 0 && candiantes.push(dp[j - kvolumn] + kvalue);
            }
            
            dp[j] = Math.max(...candiantes);
        }
    }

    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

参考：

• 题目链接