题解 | #购物单#

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

//0-1背包问题
int main() {
    int N, m;    //m个商品，附件绑定主件
    int weight[60][3] = {0};   //3中情况：主件，附件1，附件2，weight是v
    int value[60][3] = {0};    //value是p
    if(cin>>N>>m){
        int dp[60][32000] = {0};
        // N /= 10;   //都是10的整数倍 节约空间
        int v,p,q;
        for(int i=1;i<=m;i++){
            cin>>v>>p>>q;   
            p = p*v;
            // v /= 10;
            //按主件-附件分类  第二个小标表示是第i件物品还是主件附件
            if(q == 0){    //仅主件
                weight[i][q] = v;
                value[i][q] = p;
            }
            else if(weight[q][1]==0){     //指针指向商品q，第二个角标1表示主件的附件1
                weight[q][1] = v;
                value[q][1] = p;
            }
            else{
                weight[q][2] = v;
                value[q][2] = p;
            }
        }

        //动态规划,dp[i][j]表示前i个商品，预算为j的情况下，能得到的最大满意度
        for(int i=1;i<=m;i++){
            for(int j=1;j<=N;j++){
                int max_i = dp[i-1][j];
                //遍历每种情况
                if(weight[i][0] <= j){  //第一种情况，只有主件
                    max_i = max(max_i, dp[i-1][j-weight[i][0]] + value[i][0]);
                    // if(t > dp[i-1][j])
                    // dp[i][j] = max_i;  
                }
                if(weight[i][0] + weight[i][1] <= j){   //第二种情况，有主件+附件1
                    max_i = max(max_i, dp[i-1][j-weight[i][0]-weight[i][1]] + value[i][0] + value[i][1]);
                    // if(t > dp[i-1][j])
                    // dp[i][j] = max_i;
                }
                if(weight[i][0] + weight[i][2] <= j){    //第三种情况，有主件+附件2
                    max_i = max(max_i, dp[i-1][j-weight[i][0]-weight[i][2]] + value[i][0] + value[i][2]);
                    // if(t > dp[i-1][j])
                    // dp[i][j] = max_i;
                }
                if(weight[i][0] + weight[i][1] +weight[i][2] <= j){    //第四种情况，有主件+附件1+附件2
                    max_i = max(max_i, dp[i-1][j-weight[i][0]-weight[i][1]-weight[i][2]] + value[i][0] + value[i][1] + value[i][2]);
                    // if(t > dp[i-1][j])
                    // dp[i][j] = max_i;
                }
                dp[i][j] = max_i;
            }

            
        }
        cout<<dp[m][N]<<endl;

        return 0;



    }
}
// 64 位输出请用 printf("%lld")