题解 | #购物单#

#include <iostream>
#include <vector>
using namespace std;
//本题在标准01背包问题的基础上加了约束条件，物品间存在最高为一层的依赖关系且单物品最多有两个附件
//考虑如何转化成标准背包问题，定义结构体把附件存到主件下，相当于在背包问题大框架下，把对单一物品的dp[i][j]状态转移过程变为对物品组的状态转移，用01代表物品组合即：100,110,101,111，对这四种情况分别考虑

struct Item {
    //用来存物品的价格和价值，因为一件物品的附件最多两个，所以只存主件个数个Item，附件存在对应主件下
    //此处不能用vector<int> prices(3,0)的格式，因为结构体内不允许直接初始化非静态成员变量,这种格式只能用于局部变量

    //下面这两种写法都可以
    vector<int> prices = vector<int>(3, 0);
    int values[3] = {0, 0, 0};
};
int main() {
    int N, m;
    while (cin >> N >> m) {
        N /= 10;//因为价格均为10的倍数，所以把资金和价格全都除以10可以减少计算量
        vector<Item>items(61);
        for (int i = 1; i <= m; ++i) {//下标从1开始
            int a, b, c;
            cin >> a >> b >> c;
            a /= 10;
            b *= a;
            if (c == 0) {//主件
                items[i].prices[0] = a;
                items[i].values[0] = b;
            } else {//第一附件，存到主件对应的结构体内
                //因为所有的Item结构体都已初始化为0了，所以附件序号对应的那个结构体均为0，不影响dp计算
                if (items[c].prices[1] == 0) {
                    items[c].prices[1] = a;
                    items[c].values[1] = b;
                } else { //第二附件
                    items[c].prices[2] = a;
                    items[c].values[2] = b;
                }
            }
        }
        // 在经典0/1背包框架下，添加主件组内的判断
        vector<vector<int> > dp(m + 1, vector<int>(N + 1, 0));//下标全从1开始
        //dp[i][j]代表前i件物品在预算为j时能获得的最大价值
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= N; ++j) {
                //把每个主件组的价格价值提取出来（附件对应的组均为0）
                int a = items[i].prices[0], b = items[i].values[0];
                int c = items[i].prices[1], d = items[i].values[1];
                int e = items[i].prices[2], f = items[i].values[2];
                if (j >= a) {
                    //剩余预算足够当前主件，结果会参与后三个附件组合的判断
                    dp[i][j] = max(dp[i - 1][j - a] + b, dp[i - 1][j]);
                } else {
                    //不够的话取上一物品对应的值，后三个判断都不会影响到dp[i][j]
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                if (j >= a + c) {
                    dp[i][j] = max(dp[i - 1][j - a - c] + b + d, dp[i][j]);
                }
                if (j >= a + e) {
                    dp[i][j] = max(dp[i - 1][j - a - e] + b + f, dp[i][j]);
                }
                if (j >= a + c + e) {
                    dp[i][j] = max(dp[i - 1][j - a - c - e] + b + d + f, dp[i][j]);
                }
                //简化写法如下：
                // dp[i][j] = j >= a ? max(dp[i - 1][j - a] + b, dp[i - 1][j]) : dp[i - 1][j];
                // dp[i][j] = j >= (a + c) ? max(dp[i - 1][j - a - c] + b + d,
                //                               dp[i][j]) : dp[i][j];
                // dp[i][j] = j >= (a + e) ? max(dp[i - 1][j - a - e] + b + f,
                //                               dp[i][j]) : dp[i][j];
                // dp[i][j] = j >= (a + c + e) ? max(dp[i - 1][j - a - c - e] + b + d + f,
                //                                   dp[i][j]) : dp[i][j];
            }
        }
        cout << dp[m][N] * 10 << endl;//结果还原乘10
    }
  return 0;
}