题解 | #购物单#

不使用第一个dim，直接用1dim的dp数组来做的，

是0-1背包问题的，做了些改动的，主要是多了附件，若是没有附件的话，就是标准的0-1背包问题的；

附件的处理是最重要的，用map记录了附件，通过map可以直接查询出每个主件包括的所有附件

在0-1背包的基础上，需要在第二层循环，加入附件的，然后看加入附件以后的收益，和之前的收益，拿到最大值就可以

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
int main(void) {
    /*
    是0-1背包问题的，做了些改动的，主要是多了附件，若是没有附件的话，就是标准的0-1背包问题的；
    附件的处理是最重要的，用map记录了附件，通过map可以直接查询出每个主件包括的所有附件
    在0-1背包的基础上，需要在第二层循环，加入附件的，然后看加入附件以后的收益，和之前的收益，拿到最大值就可以
    */
    int i, j, k, m, n, x, y, z, N, tmp;
    cin>>N>>m;
    N = N/10;
    vector<vector<int>> arr(m, vector<int>(3, 0));
    unordered_map<int, vector<int>> mp;     // 用来保存每个附件
    vector<int> fujian;
    for(j = 0; j < m; j++) {
        scanf("%d %d %d", &arr[j][0], &arr[j][1], &arr[j][2]);
        arr[j][0] = arr[j][0] / 10;
        if(arr[j][2]!=0) {
            mp[arr[j][2] - 1].push_back(j);
        }
    }
    vector<int> dp(N+1, -0xffffff);
    dp[0] = 0;    // 初始化最开始的数值到 0
    for(i = 0; i < m; i++) { // 遍历每个物品，因dp不需要考虑第一个dim，所以这里没问题，否则需要另外修改的
        fujian = mp[i];  // 拿出该主件对应的所有附件
        if(arr[i][2]!=0) { // 附件直接跳过，下个循环内单独处理的
            continue;
        }
        for(j = N; j >= arr[i][0]; j--) {   // 遍历合适的体积-钱
            dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][0] * arr[i][1]); // 算加入主件或者不加入的最大收益
            if(fujian.size() > 0) {   // 附件的个数 >= 1
                y = fujian[0];  // 拿出附件1的标号 index
                if(j - arr[i][0] - arr[y][0] >= 0)  // 加入两件的，主件和附件1，以及不加入的最大收益，实际的i需要+1，但是省略了第一个dim
                    dp[j] = max(dp[j], dp[j - arr[i][0] - arr[y][0]] + arr[i][0] * arr[i][1] + arr[y][0] * arr[y][1]);
            }
            if(fujian.size() > 1) { // 附件的个数 = 2
                z = fujian[1];   // 拿出附件2的标号 index
                if(j - arr[i][0] - arr[z][0] >= 0)  // 加入两件的，主件和附件2，以及不加入的最大收益，实际的i需要+1，但是省略了第一个dim
                    dp[j] = max(dp[j], dp[j - arr[i][0] - arr[z][0]] + arr[i][0] * arr[i][1] + arr[z][0] * arr[z][1]);
                if(j - arr[i][0] - arr[y][0] - arr[z][0] >= 0)   // 加入三件的，主件和附件1和附件2，以及不加入的最大收益，实际的i需要+2，但是省略了第一个dim
                    dp[j] = max(dp[j], dp[j - arr[i][0] - arr[y][0] - arr[z][0]] + arr[i][0] * arr[i][1] + arr[y][0] * arr[y][1] + arr[z][0] * arr[z][1]);
            }
        }
    }
    vector<int>::iterator it = max_element(dp.begin(), dp.end());
    cout<<it[0] * 10;
    return 0;
}