题解 | 购物单

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

int main() {
    int n, m;
    cin >> n >>m;
    n /= 10;
    vector<vector<int>> prices(m+1, vector<int>(3, 0)); // 第0列是主物品自身的price，第1、2列是附属物品的price(如有)
    vector<vector<int>> satisfy(m+1, vector<int>(3, 0));
    for(int i = 1; i<=m; i++) {
        int a, b, c;
        cin >> a >>b>>c;
        a/=10; b = b*a;
        if (c == 0) {
            // 主物品
            prices[i][0] = a;
            satisfy[i][0] = b;
        } else {
            // 附属物品，我要把它放到对应的主物品里面
            if (prices[c][1] == 0) {
                prices[c][1] = a;
                satisfy[c][1] = b;
            } else {
                prices[c][2] = a;
                satisfy[c][2] = b;
            }
        }
    }

    // cout << "hello";
    // 设置好了所有主物品的信息

/*
    // 求解前i个主物品，在容量为j的情况下，能获得的最大满意度
    // 根据第i个物品是否取用，分为两种情况：
         1. 不取用，则问题变成前i-1个主物品在容量为j的情况下取得的最大满意度
         2. 取用：
                此时如果不考虑附属物品的问题，那就是纯粹的01背包了；前面i-1个主物品在j-第i个物品的容量下的最大满意度，再加上第i个物品所取得的满意度。
                进一步考虑附属物品的问题：其实就是取用的场景可以进一步划分为4种情况：
                    1.不取附属物品。
                    2.只取附属物品1
                    3.只取附属物品2
                    4.同时取附属物品1和2
*/

// 大的框架并没有跳出01背包问题：最终就是求前m个主物品，在容量为n下能取得的最大满意度。

    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for(int i = 1; i<=m; i++) {
        for(int j = 1; j<=n; j++) {
            // 求dp[i][j]的值
            int p = prices[i][0], s = satisfy[i][0];           
            int sub1_p = prices[i][1], sub1_s = satisfy[i][1];
            int sub2_p = prices[i][2], sub2_s = satisfy[i][2];

            // 不取
            dp[i][j] = dp[i-1][j];

            // 取
            dp[i][j] = j >= p ? max(dp[i][j], dp[i-1][j-p]+s) : dp[i][j];
            dp[i][j] = j >= (p+sub1_p) ? max(dp[i][j], dp[i-1][j-p-sub1_p] + s + sub1_s) : dp[i][j];
            dp[i][j] = j >= (p+sub2_p) ? max(dp[i][j], dp[i-1][j-p-sub2_p] + s + sub2_s) : dp[i][j];
            dp[i][j] = j >= (p+sub1_p+sub2_p) ? max(dp[i][j], dp[i-1][j-p-sub1_p-sub2_p]+s+sub1_s+sub2_s) : dp[i][j];
            // cout << dp[i][j] << endl;
        }
    }
    cout << dp[m][n]*10;
}
// 64 位输出请用 printf("%lld")