题解 | 购物单

#include <iostream>
#include<vector>
//#include<cmath>
using namespace std;

int main()
{
    //是传统的01背包问题的变形，只用处理主件，在处理每一个主件时，都要分四种情况来考虑，分别是只有主件，主件和附件一，主件和附件二，主件和附件一二，附件不用单独考虑。类似于分组背包问题，把附件和主件作为一个组，每个组中有最多四个情况进行四选一操作
    //创建物品类
    class item {
    public:
        int v;//价格
        int m;//满意度
        int q;//主件编号
    };
    int n, m;//预算和物品总数
    cin >> n >> m;
    vector<vector<item>>group(m);//分组存储item
    int count = 0;//主件的个数
    for (int i = 0; i < m; i++)//循环存放m个物品到group中
    {
        item tmp;
        int w = 0;
        cin >> tmp.v >> w >> tmp.q;
        if (tmp.q == 0)
            count++;
        tmp.m = tmp.v * w;
        group[i].push_back(tmp);
    }
    //将每一个附件和其对应的主件组成一个分组
    for (auto it : group)
    {
        if (it[0].q == 0)//主件不处理
            continue;
        else//附件则找对应主件进行组合
        {
            int index = it[0].q;//对应的主件编号
            //主件和附件组合
            int size = group[index - 1].size(); // 当前主件的组合数
            for (int k = 0; k < size; k++)
            {
                item fix;
                fix.q = group[index - 1][k].q;
                fix.v = group[index - 1][k].v +it[0].v;
                fix.m = group[index - 1][k].m + it[0].m;
                group[index - 1].push_back(fix);
            }
        }
    }
	//一维数组实现,dp[j]表示当前预算为j时的最大价值
	vector<int> dp(n + 1, 0);
    for (int i = 0; i < m; i++)
    {
        if (group[i][0].q != 0)
            continue;//不处理只有附件的组
        for(int j = n; j>=group[i][0].v ; j--)//逆向遍历数组防止重复选择物品
            for (auto it : group[i])//依次判断组中的每种情况
            {
                if (j >= it.v)
                {
                    dp[j] = max(dp[j], dp[j - it.v] + it.m);
                }
            }
    }
    cout << dp[n];
}