ACM. HJ16 购物单 ●●

HJ16 购物单 ●●

描述

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。

每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。

王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。

满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第 $i$ 件物品的价格为 $v[i]$，重要度为 $w[i]$，共选中了 $k$ 件物品，编号依次为$j_1,j_2,...,j_k$，则满意度为：$v[j_1]\ast w[j_1]+v[j_2]\ast w[j_2]+\dots +v[j_k]\ast w[j_k]$。

请你帮助王强计算可获得的最大的满意度。

输入描述：

输入的第 1 行，为两个正整数N，m，用一个空格隔开：

（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q

（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。
如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）

输出描述：

输出一个正整数，为张强可以获得的最大的满意度。

示例

输入：
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0
输出：
130
说明：
由第1行可知总钱数N为50以及希望购买的物品个数m为5；
第2和第3行的q为5，说明它们都是编号为5的物品的附件；
第4 ~ 6行的 q 都为0，说明它们都是主件，它们的编号依次为3~5；
所以物品的价格与重要度乘积的总和的最大值为 10 * 1 + 20 * 3 + 20 * 3 = 130

题解

1. 动态规划（01背包）

0-1背包问题
问题描述：有一个背包可以装物品的总重量为W，现有N个物品，每个物品中w[i]，价值v[i]，用背包装物品，能装的最大价值是多少？
定义状态转移数组dp[i][j]，表示前 i 个物品，背包重量为 j 的情况下能装的最大价值。
状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
即当前第 i 个物品要么放入背包，要么不放入背包。

购物单问题本质上还是01背包问题，只不过多了主件和附件的关系，如果不看附件，那么就与01背包问题一样；而此处附件的购买要依赖于主件。

因此有多种不同的情况需要考虑：
1、不买主件（及附件）；
2、只买主件；
3、买主件 + 附件（又分多种情况）。

因为本题中主件最多有 2 个附件，因此在输入数据时，对数据进行特殊处理，将附件放置在对应的主件数组后面，凸显依赖关系；
同时对价格数量统一除以10，减小计算量；此外还能将满意度（价格 * 重要度）预先计算存储在数组中

我们可以这样理解，对于同一个物品，现在它的价格、重要度都是可变的；
那么我们只需要对每一个主件尝试如下四种情况：

1. 仅加入一个主件；
2. 加入主件和第一个附件；
3. 加入主件和第二个附件；
4. 加入主件和两个附件；

w[i][k]表示第 i 个物品的第 k 种情况，k 的取值范围 0~3，分别对应以上四种情况，v[i][k]表示第 i 个物品对应第 k 种情况的价值，现在就把购物车问题转化为了0-1背包问题，即在以上四种情况中找到最大值。

1. dp[i][j] 表示用 j * 10 元购买 i 个主件（包括其附件）中的东西时得到的最大满意度；

2. dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i][k]]+v[i][k])
dp[i-1][j]表示当前物品不放入背包，w[i][k]表示第 i 个主件对应第 k 中情况，即当前第 i 个物品的四种情况中价值最大的要么放入背包，要么不放入背包。
   即dp[i][j] = max(物品不放入背包，主件，主件+附件1，主件+附件2，主件+附件1+附件2)

3. 初始化为 0；

4. 外层为主件物品数，内层为可花费金额。

• 时间复杂度：$O(m\ast N)$，双层循环
• 空间复杂度：$O(m\ast N)$，需要一个二维额外数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int money, n;
    while(cin >> money >> n){
        vector<vector<int>> things(n, vector<int>(6, 0));
        money /= 10;                                  // 金额统一 / 10，减小计算
        int masterNum = 0;                            // 主件数量
        for(int i = 0; i < n; ++i){
            int cost, important, master;
            cin >> cost >> important >> master;
            if(master == 0){                          // 主件
                things[i][0] = cost/10;
                things[i][1] = important * cost;      // 物品满意度提前计算，减少乘法计算次数
                ++masterNum;
            }else if(things[master-1][2] == 0){       // 附件1 加入到主件数组中
                things[master-1][2] = cost/10; 
                things[master-1][3] = important * cost;
            }else{                                    // 附件2 加入到主件数组中
                things[master-1][4] = cost/10;
                things[master-1][5] = important * cost;
            }
        }
        vector<vector<int>> dp(masterNum+1, vector<int>(money+1, 0));    // 动态规划数组
        int masterIndex = 0;                        
        for(int i = 0; i < n; ++i){
            if(things[i][0] == 0) continue;         // 非主件，跳过
            ++masterIndex;                          // 只遍历主件，记录主件索引
            for(int j = 1; j <= money; ++j){
                int masterCost = things[i][0];      // 花费
                int attCost1 = things[i][2];
                int attCost2 = things[i][4];
                int masterSat = things[i][1];       // 满意度
                int attSat1 = things[i][3];
                int attSat2 = things[i][5];

                if(j >= masterCost){                // 先考虑主件，买 或 不买
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost] + masterSat, 
                                                    dp[masterIndex-1][j]);
                }else{
                    dp[masterIndex][j] = dp[masterIndex-1][j];		// 该步还与dp[masterIndex-1][j]比较
                }
    
                if(attCost1 > 0 && j >= masterCost + attCost1){    // 考虑主件+附件1组合，买 或 不买
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost-attCost1] + masterSat + attSat1, 
                                                    dp[masterIndex][j]);
                }else{
                    dp[masterIndex][j] = dp[masterIndex][j];
                }

                if(attCost2 > 0 && j >= masterCost + attCost2){    // 考虑主件+附件2组合，买 或 不买
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost-attCost2] + masterSat + attSat2, 
                                                    dp[masterIndex][j]);
                }else{
                    dp[masterIndex][j] = dp[masterIndex][j];
                }

                if(attCost2 > 0 && j >= masterCost + attCost1 + attCost2){    // 考虑主件+附件1+附件2组合，买 或 不买
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost-attCost1-attCost2] + masterSat + attSat1 + attSat2, 
                                                    dp[masterIndex][j]);
                }else{
                    dp[masterIndex][j] = dp[masterIndex][j];
                }  
            }    // 最终得到 dp[i][j] = max(物品不放入背包，主件，主件+附件1，主件+附件2，主件+附件1+附件2)
            if(masterIndex == masterNum) break;        // 主件已遍历完毕
        }
        cout << dp[masterNum][money] << endl;
    }

    return 0;
}
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

• 一维滚动数组优化 O(m)

1. dp[j] 表示有 j * 10元时可得到的最大满意度；
2. dp[j] = max(dp[j], dp[j-w[i]] + v[i]); 其中 w[i] 和 v[i] 有四种不同的情况
3. dp[0] = 0;
4. 先物品，再金额，金额从大到小遍历。
   倒序遍历金额是为了保证物品 i 只被放入一次！
   dp[j-w[i]]+v[i] 正序遍历时前面的值被更新，会导致重复取物品。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int money, n;
    while(cin >> money >> n){
        vector<vector<int>> things(n, vector<int>(6, 0));
        money /= 10;                                  // 金额统一 / 10，减小计算
        int masterNum = 0;                            // 主件数量
        for(int i = 0; i < n; ++i){
            int cost, important, master;
            cin >> cost >> important >> master;
            if(master == 0){                          // 主件
                things[i][0] = cost/10;
                things[i][1] = important * cost;      // 物品满意度提前计算，减少乘法计算次数
                ++masterNum;
            }else if(things[master-1][2] == 0){       // 附件1 加入到主件数组中
                things[master-1][2] = cost/10; 
                things[master-1][3] = important * cost;
            }else{                                    // 附件2 加入到主件数组中
                things[master-1][4] = cost/10;
                things[master-1][5] = important * cost;
            }
        }
        vector<int> dp(money+1, 0);    // 动态规划数组
        int masterIndex = 0;                        
        for(int i = 0; i < n; ++i){
            if(things[i][0] == 0) continue;         // 非主件，跳过
            ++masterIndex;                          // 只遍历主件，记录主件索引
            for(int j = money; j >= 1; --j){		// 倒序遍历！！！
                int masterCost = things[i][0];      // 花费
                int attCost1 = things[i][2];
                int attCost2 = things[i][4];
                int masterSat = things[i][1];       // 满意度
                int attSat1 = things[i][3];
                int attSat2 = things[i][5];

                if(j >= masterCost){                // 先考虑主件，买 或 不买
                    dp[j] = max(dp[j-masterCost] + masterSat, dp[j]);
                }
    
                if(attCost1 > 0 && j >= masterCost + attCost1){    // 考虑主件+附件1组合，买 或 不买
                    dp[j] = max(dp[j-masterCost-attCost1] + masterSat + attSat1, dp[j]);
                }

                if(attCost2 > 0 && j >= masterCost + attCost2){    // 考虑主件+附件2组合，买 或 不买
                    dp[j] = max(dp[j-masterCost-attCost2] + masterSat + attSat2,  dp[j]);
                }

                if(attCost2 > 0 && j >= masterCost + attCost1 + attCost2){    // 考虑主件+附件1+附件2组合，买 或 不买
                    dp[j] = max(dp[j-masterCost-attCost1-attCost2] + masterSat + attSat1 + attSat2, dp[j]);
                } 
            }    // 最终得到 dp[j] = max(物品不放入背包，主件，主件+附件1，主件+附件2，主件+附件1+附件2)
            if(masterIndex == masterNum) break;        // 主件已遍历完毕
        }
        cout << dp[money] << endl;
    }

    return 0;
}
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