题解 | #购物单#

动态规划

难点：

1. 输入问题，输入数列的定义
2. dp判定的问题，如何将附件和主件合并起来用0-1背包的解法解决

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    vector<vector<int> > price(61, vector<int>(3, 0)); // 价格
    vector<vector<int> > priority(61, vector<int>(3, 0)); // 重要度
    
    int x, y, z; // 输入
    for (int i=1; i<=m; i++) {
        cin >> x >> y >> z;
        
        y = x*y;
        if (z == 0) {
            price[i][0] = x;
            priority[i][0] = y;
        }
        else {
            // 附件最多只有两种
            // 输入附件1
            if (price[z][1] == 0) {
                price[z][1] = x;
                priority[z][1] = y;
            }
            // 输入附件2
            else {
                price[z][2] = x;
                priority[z][2] = y;
            }
        }
    }
    
    // 使用分组背包
    vector<vector<int> > dp(m+1, vector<int>(N+1, 0));
    // dp[i][j] = max(dp[i-1][])
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=N; j++) {
            if (j>=price[i][0]) {// 只买主件
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-price[i][0]]+priority[i][0]);
            }
            else {
                // 不买主件
                dp[i][j] = dp[i-1][j];
            }
            
            // 买主件+附件1
            if (j>=price[i][0]+price[i][1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-price[i][0]-price[i][1]]+priority[i][0]+priority[i][1]);
            }
            // 买主件+附件2
            if (j>=price[i][0]+price[i][2]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-price[i][0]-price[i][2]]+priority[i][0]+priority[i][2]);
            }
            // 买主件+附件1+附件2
            if (j>=price[i][0]+price[i][1]+price[i][2]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-price[i][0]-price[i][1]-price[i][2]]+priority[i][0]+priority[i][1]+priority[i][2]);
            }
        }
    }
    
    cout << dp[m][N];
    
    
    
    return 0;
}