题解 | #购物单#C++解题，转换为0-1背包耗时4ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//解题思路，
//1、首先通过一系列操作提取出每个主件及其附件的价格和重要度；
//2、将该问题转化为0-1背包问题，每次判断当前位置在某一个价格下的最大满意度时，假设存在两个主件，
//考虑的是四种情况即：1、选择该位置主件；2、选择该位置主件+第一个附件；3、选择该位置主件+第二个附件；4、选择该位置主件+第一二附件；
int main()
{
    int N,m;
    cin >> N >> m;
    N /= 10;
    vector<vector<int>> things(m,vector<int>(6,0));
    vector<bool> flag(m,false);
    int a,b,c;
    for(int i=0;i<m;i++)
    {
        cin >> a >> b >> c;
        if(c == 0)
        {
            things[i][0] = a / 10;
            things[i][1] = b;
            flag[i] = true;
        }else
        {
            if(things[c-1][2] == 0)
            {
                things[c-1][2] = a/10;
                things[c-1][3] = b;
            }else{
                things[c-1][4] = a/10;
                things[c-1][5] = b;
            }
        }
    }
    vector<vector<int>> price;
    vector<vector<int>> value;
    for(int i=0;i<m;i++)
    {
        if(flag[i])
        {
            vector<int> tmp1,tmp2;
            for(int j=0;j<things[i].size();j+=2)
            {
                tmp1.push_back(things[i][j]);
                tmp2.push_back(things[i][j+1]);
            }
            price.push_back(tmp1);
            value.push_back(tmp2);
        }
    }
    int M = price.size();
    vector<vector<int>> dp(M+1,vector<int>(N+1,0));
    int price0,price1,price2,val0,val1,val2;
    for(int i=1;i<=M;i++)
    {
        for(int j=1;j<=N;j++)
        {
            price0 = price[i-1][0];
            price1 = price[i-1][1];
            price2 = price[i-1][2];
            val0 = value[i-1][0];
            val1 = value[i-1][1];
            val2 = value[i-1][2];
            if(j >= price0)
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-price0]+price0*val0);
            else
                dp[i][j] = dp[i-1][j];
            if(price1>0 && j >= price0+price1)
                dp[i][j] = max(dp[i][j],dp[i-1][j-price0-price1]+price0*val0+price1*val1);
            if(price2>0 && j >= price0+price2)
                dp[i][j] = max(dp[i][j],dp[i-1][j-price0-price2]+price0*val0+price2*val2);
            if(price1>0 && price2>0 && j >= price0+price1+price2)
                dp[i][j] = max(dp[i][j],dp[i-1][j-price0-price1-price2]+
                                      price0*val0+price1*val1+price2*val2);
        }
    }
    cout << dp[M][N]*10 << endl;
    return 0;
}