487 金明的预算方案（分组背包问题扩展）

不念不忘少年蓝@ 2022-09-11 04:16 148阅读 0赞

**1. 问题描述：**

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说："你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行"。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16][]

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v\[j\]，重要度为w\[j\]，共选中了k件物品，编号依次为j1，j2，…，jk，则所求的总和为：  
v\[j1\] ∗ w\[j1\] + v\[j2\] ∗ w\[j2\] +… + v\[jk\] ∗ w\[jk\]（其中\*为乘号）  
请你帮助金明设计一个满足要求的购物单。

**输入格式**

输入文件的第1行，为两个正整数，用一个空格隔开：N m，其中N表示总钱数，m为希望购买物品的个数。从第2行到第m+1行，第j行给出了编号为j - 1的物品的基本数据，每行有3个非负整数v p q，其中v表示该物品的价格，p表示该物品的重要度（1~5），q表示该物品是主件还是附件。  
如果q = 0，表示该物品为主件，如果q > 0，表示该物品为附件，q是所属主件的编号。

**输出格式**

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

**数据范围**

N < 32000，m < 60，v < 10000

**输入样例：**

1000 5  
800 2 0  
400 5 1  
300 5 1  
400 3 0  
500 2 0

**输出样例：**

2200  
来源：[https://www.acwing.com/problem/content/description/489/][https_www.acwing.com_problem_content_description_489]

**2. 思路分析：**

分析题目可以知道这道题目属于**分组背包问题**一个扩展，我们可以将每一个主件与对应的附件看成一组，在每一组中可以选择主件与若干个附件（选择了某个组中的附件之后一定要选择主件），我们需要求解的是在不超过总金额N的前提下选择的所有物品中物品的价格与重要度乘积的总和的最大值，类似于分组背包问题，我们可以尝试每一组中所有可能的选择方案来更新对应金额能够获得的总价值。其中需要声明一个二维数组或者列表，其中dp\[i\]\[j\]表示前i组物品中总金额不超过j的前提下能够获得的最大价值，可以发现在状态计算的时候我们使用的只是上一个状态的值所以我们可以将二维数组优化为一维数组，其中dp\[i\]表示总金额不超过i的前提下能够获得的最大价值；状态计算的时候需要使用四层循环进行枚举，第一层循环枚举所有的物品组，每一个组中对应主件和附件，第二层循环枚举总金额（相当于枚举的是体积），因为使用的是一维数组而且在状态计算的时候使用的是上一个状态的值所以需要逆序遍历体积，第三层循环枚举所有可能的选择方案，需要枚举1 << len(servent\[i\])，表示附件数量为len(servent\[i\])所有的选择情况，每一个数字对应的二进制中对应的0和1表示对应位置附件是否选择，枚举所有的选择方案来更新对应的dp数组对应金额的值即可，最终的dp\[N\]就是我们要求解的答案。

**3. 代码如下：**

**python：**

if __name__ == '__main__':
        # 分组背包问题扩展, m表示总钱数, n表示物品的个数
        m, n = map(int, input().split())
        # 存储主件对应的价格和对应的权重
        master = [list() for i in range(n + 1)]
        # 存储附件编号
        servent = [list() for i in range(n + 1)]
        # 先存储对应的主件与附件中对应的编号
        for i in range(1, n + 1):
            v, p, q = map(int, input().split())
            if q > 0:
                # 附件
                servent[q].append([v, v * p])
            else:
                master[i].append([v, v * p])
        dp = [0] * (m + 1)
        for i in range(1, n + 1):
            # 因为使用到的是上一次的状态所以优化为一维之后需要逆序枚举体积
            for j in range(m, -1, -1):
                # 二进制枚举, 枚举所有可能的选择情况, 例如附件数目为2那么可能的选择情况为2 ^ n所以枚举这些数字对应位置是否为1来选择对应的物品
                for k in range(1 << len(servent[i])):
                    v, w = 0, 0
                    if len(master[i]) > 0:
                        v += master[i][0][0]
                        w += master[i][0][1]
                    for u in range(len(servent[i])):
                        # 判断当前这一位是否是1, 右移然后与1相与即可判断当前的第u位是否是1
                        if k >> u & 1:
                            v += servent[i][u][0]
                            w += servent[i][u][1]
                    if j >= v:
                        dp[j] = max(dp[j], dp[j - v] + w)
        print(dp[m])

**c++：**

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #define v first
    #define w second
    using namespace std;
    typedef pair<int, int> PII;
    
    const int N = 60, M = 32010;
    
    int n, m;
    PII master[N];
    vector<PII> servent[N];
    int f[M];
    
    int main()
    {
        cin >> m >> n;
        for (int i = 1; i <= n; i ++ )
        {
            int v, p, q;
            cin >> v >> p >> q;
            p *= v;
            if (!q) master[i] = {v, p};
            else servent[q].push_back({v, p});
        }
    
        for (int i = 1; i <= n; i ++ )
            for (int u = m; u >= 0; u -- )
            {
                for (int j = 0; j < 1 << servent[i].size(); j ++ )
                {
                    int v = master[i].v, w = master[i].w;
                    for (int k = 0; k < servent[i].size(); k ++ )
                        if (j >> k & 1)
                        {
                            v += servent[i][k].v;
                            w += servent[i][k].w;
                        }
                    if (u >= v) f[u] = max(f[u], f[u - v] + w);
                }
        }
    
        cout << f[m] << endl;
        return 0;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fe95d4e796584265965d2248c6e6bbb9.png
[https_www.acwing.com_problem_content_description_489]: https://www.acwing.com/problem/content/description/489/