题解 | #购物单#

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

int dp[3210];
int main() {
    int N, m;   //N:总钱数， m:可购买物品个数
    cin >> N >> m;
    N/=10;
    vector<vector<int>> weight(m+1, vector<int>(3,0));
    vector<vector<int>> value(m+1, vector<int>(3,0));
    for(int i = 1; i <= m; i++){
        int w,v,t;
        cin >> w >> v >> t;
        v *= w;
        w/=10;
        if(!t){
            weight[i][0] = w;
            value[i][0] = v;
        }else if(!weight[t][1]){
            weight[t][1] = w;
            value[t][1] = v;
        }else{
            weight[t][2] = w;
            value[t][2] = v;
        }
    }

    for(int i = 1; i <= m; i++){
        for(int j = N; j > 0; j--){
            int tw = weight[i][0];
            int tv = value[i][0];
            if(j >= tw){
                dp[j] = std::max(dp[j], dp[j-tw] + tv);
            }
            tw = weight[i][0] + weight[i][1];
            tv = value[i][0] + value[i][1];
            if(weight[i][1] && j >= tw){
                dp[j] = std::max(dp[j], dp[j-tw] + tv);
            }
            tw = weight[i][0] + weight[i][2];
            tv = value[i][0] + value[i][2];
            if(weight[i][2] && j >= tw){
                dp[j] = std::max(dp[j], dp[j-tw] + tv);
            }
            tw = weight[i][0] + weight[i][1]+ weight[i][2];
            tv = value[i][0] + value[i][1]+ value[i][2];
            if(weight[i][2] && j>= tw){
                dp[j] = std::max(dp[j], dp[j-tw] + tv);
            }
        }
    }
    cout << dp[N];
    return 0;
}
// 64 位输出请用 printf("%lld")

转换为01背包问题：假设只有主件，附件作为遍历每个主件时的多种情况考虑，即假定每个主件有不同的价格和满意度，每次考虑是否购买一个组件时，同时考虑以下4种情况：只买主件，买主件和附件1，买主件和附件2，买主件、附件1和附件2。