背包问题学习笔记-二维费用的背包问题

题意描述：

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

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

输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

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

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

数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

示例：

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

8

---

解题思路：
Alice: 这题居然是中等难度 ？
Bob：咋了，你觉得应该是困难还是简单 ？
Alice：我看这题就是 01 背包加了一个维度，相当了多了一种体积。这个直接把原来 01 背包的代码扩展一下应该就行了吧。
Bob：考虑第 i 个物品，体积是 j，重量是 k 的情况，dp[i][j][k] = max( dp[i-1][j][k], dp[i-1][j-vi][k-mi] + wi)，其实还是第 i 个物品选不选，然后直接套一维 01 背包的状态压缩，从最大体积，最大重量往小计算，搞一个二维数组应该就行了。
Alice: 会超时吗 ？
Bob: 三重循环的话，1000 * 100 * 100 大概 10^7，应该刚好能过。
Alice: 可以试试，而且实际的计算次数应该达不到 10^7，第 i 个物品实际计算量应该是 (maxVolumn - vi) * (maxWeight - mi)
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)));
    });
    return list;
}

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


const solve = (count, maxVolum, maxWeight, volumAndWeightAndValue) => {
    
    const dp = [];
    for(let i=0; i<maxVolum+10; ++i) {
        dp.push(new Array(maxWeight + 10).fill(0));
    }
    
    for(let i=0; i<count; ++i){
        // 第 i 个物品的体积，重量和价值
        const [ivolum, iweight, ivalue] = volumAndWeightAndValue[i];
        for(let j=maxVolum; j>=ivolum; --j) {
            for(let k=maxWeight; k>=iweight; --k) {
                dp[j][k] = Math.max(dp[j][k], dp[j-ivolum][k-iweight] + ivalue);
            }
        }
    }
    
    
    console.log(dp[maxVolum][maxWeight]);
}

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

参考：

• 题目链接