题解 | #购物单#

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(int argc,char* argv[])
{
    //0-1背包中的最大值问题
    int N=0,m=0;
    while(cin>>N>>m)
    {
        N /= 10; // 由于所有的价格都是10的整倍数，所以可以均除10以简化运算复杂度
        vector<vector<long> > value(m+1,vector<long>(3,0));
        vector<vector<long> > weight(m+1,vector<long>(3,0));
        int v=0,p=0,q=0;
        for(int i=1;i<=m;i++)
        {
            cin>>v>>p>>q;
            if(q==0){//主件
                value[i][0]=v/10;
                weight[i][0]=v/10*p;
            }else if(value[q][1]==0){
                value[q][1]=v/10;
                weight[q][1]=v/10*p;
            }else{
                value[q][2]=v/10;
                weight[q][2]=v/10*p;
            }
        }
        vector<int> dp(N+1,0);
        int value_total = 0,weight_total = 0;
        for(int i=1;i<=m;i++)
        {
            for(int j=N;j>=1;j--)
            {
                //计算主件
                value_total=value[i][0];
                weight_total=weight[i][0];
                dp[j]= j>=value_total? max(dp[j],dp[j-value_total]+weight_total):dp[j];
                //计算主件+附件1
                value_total=value[i][0]+value[i][1];
                weight_total=weight[i][0]+weight[i][1];
                dp[j]= j>=value_total? max(dp[j],dp[j-value_total]+weight_total):dp[j];
                //计算主件+附件2
                value_total=value[i][0]+value[i][2];
                weight_total=weight[i][0]+weight[i][2];
                dp[j]= j>=value_total? max(dp[j],dp[j-value_total]+weight_total):dp[j];
                //计算主件+附件1+附件2
                value_total=value[i][0]+value[i][1]+value[i][2];
                weight_total=weight[i][0]+weight[i][1]+weight[i][2];
                dp[j]= j>=value_total? max(dp[j],dp[j-value_total]+weight_total):dp[j];
            }
        }
        cout<<dp[N]*10<<endl;
    }
    return 0;
}