题解 | #购物单#

// 购物单
#include <bits/stdc++.h>
using namespace std;

const int N = 65;
int n, m; // n表示预算，m表示物品的数量
struct MainGoods
{
    int vi;         // 主件价格
    int pi;         // 主件重要性
    int num;        // 附件数量
    int v[2], p[2]; // v表示价格，p表示重要性
} mg[N];
int gv[N][N], gsa[N][N], gs[N]; // gv表示某组的某物品价格，gsa表示某组的某物品满意度，gs表示组中物品数量
int f[32000];                 

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) // 编号从1开始，主件编号同样使用i
    {
        int a, b, c; // a表示价格，b表示重要性，c==0表示主件，c>0表示附件编号
        cin >> a >> b >> c;
        // 主件有0，1，2个附件，按照主件分组，每组有四个物品
        if (c > 0)
        {
            mg[c].v[mg[c].num] = a;
            mg[c].p[mg[c].num] = b;
            mg[c].num++;
        }
        else
        {
            mg[i].vi = a;
            mg[i].pi = b;
        }
    }

    // 遍历所有主件生成四种物品
    int cnt = 0; // 组数
    for (int i = 1; i <= m; i++)
    {
        if (mg[i].vi == 0)
            continue;
        cnt++;
        if (mg[i].num == 0)
        {
            gs[cnt] = 1;
            gv[cnt][0] = mg[i].vi;
            gsa[cnt][0] = mg[i].vi * mg[i].pi;
        }
        else if (mg[i].num == 1)
        {
            gv[cnt][0] = mg[i].vi;
            gsa[cnt][0] = mg[i].vi * mg[i].pi;
            gv[cnt][1] = mg[i].vi + mg[i].v[0];
            gsa[cnt][1] = mg[i].vi * mg[i].pi + mg[i].v[0] * mg[i].p[0];
            gs[cnt] = 2;
        }
        else if (mg[i].num == 2)
        {
            gv[cnt][0] = mg[i].vi;
            gsa[cnt][0] = mg[i].vi * mg[i].pi;
            gv[cnt][1] = mg[i].vi + mg[i].v[0];
            gsa[cnt][1] = mg[i].vi * mg[i].pi + mg[i].v[0] * mg[i].p[0];
            gv[cnt][2] = mg[i].vi + mg[i].v[1];
            gsa[cnt][2] = mg[i].vi * mg[i].pi + mg[i].v[1] * mg[i].p[1];
            gv[cnt][3] = mg[i].vi + mg[i].v[0] + mg[i].v[1];
            gsa[cnt][3] = mg[i].vi * mg[i].pi + mg[i].v[0] * mg[i].p[0] + mg[i].v[1] * mg[i].p[1];
            gs[cnt] = 4;
        }
    }

    // 求不超过n，所能获得的最大满意度
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = n; j >= 0; j--)
        {
            // 分组背包
            for (int k = 0; k < gs[i]; k++)
            {
                if (j >= gv[i][k])
                    f[j] = max(f[j], f[j - gv[i][k]] + gsa[i][k]);
            }
        }
    }
    cout << f[n];
    return 0;
}

使用分组背包的思想：按照主件分组，将单独主件，主件+一件附件，主件+两件附件作为一个物品组，物品组中可能有四个物品，物品互斥，只能选其中一种或者不选，然后计算分组背包，思路看的背包九讲，然后试着实现一下，菜鸡轻喷