题解 | #购物单# 01背包问题的变体

#include <iostream>
#include <vector>
using namespace std;
//动态规划 0-1背包问题
//所有涉及价格的地方，由于价格全部能被10整除，全部都/10减少遍历次数，包括可供支配的总价格N、每件商品的价格price
int main() {
    int N,m;
    cin>>N>>m;
    N/=10;
    int price,priority,hash;//用来输入每件物品的价格、重要度、是否是谁的附件
    vector<vector<int>>data(m+1,vector<int>(6,0)); //用来存放商品信息，行为1～m，0行认为是无商品。存放最多m件主件商品，0、1列存放主件商品的价格和重要度，2、3列存放第一个附件（如果有）的价格和重要度，4、5列存放第二个附件（如果有）的价格和重要度
    for(int i=1;i<=m;i++){
        cin>>price>>priority>>hash;
        //如果是主件
        if(hash==0){
            data[i][0]=price/10;
            data[i][1]=priority;
        }
        else if(hash>0&&data[hash][2]==0){
            //此时这件物品是data[hash]的附件,且附件1的位置还没有登记数据，那这件商品就登记到附件1的位置
            data[hash][2]=price/10;
            data[hash][3]=priority;
        }
        else if(hash>0&&data[hash][2]!=0){
            //这件物品是data[hash]的附件，且附件1的位置已经有数据了，就放到附件2的位置
            data[hash][4]=price/10;
            data[hash][5]=priority;
        }
    }
    //初始化dp方程 dp[i][j]的含义是，总钱数为j的情况下,在[0,i]范围内购买物品所产生的最大价值（0是不购买，最大可以取到m）。初始化第一行第一列
    vector<vector<int>>dp(m+1,vector<int>(N+1,0));
    //所有的dp[i][0]=0,不需要额外再初始化了,dp[0][j]表示有j块钱的时候不购买商品，dp[0][j]=0
    //递推
    for(int i=1;i<=m;i++){
        //给每个主件商品及附件商品的价格和重要度拿出来（如果没有就是0），便于后面写递推
        int price0=data[i][0];
        int priority0=data[i][1];

        int price1=data[i][2];
        int priority1=data[i][3];

        int price2=data[i][4];
        int priority2=data[i][5];
        for(int j=1;j<=N;j++){
            //1) 只考虑买主件商品
            if(j<price0){dp[i][j]=dp[i-1][j];}//钱不够
            else{//钱够
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-price0]+price0*priority0);
            }
            //2) 再买一件附件1 dp[i][j]此时记录了购买主件后的价值，若钱不够买，dp[i][j]不变，可以省略，若钱够买，和购买附件后的价值做比较，有更大的值才赋值给dp[i][j]
           // if(j<price0+price1){dp[i][j]=dp[i][j];}//如果不够买直接值不变，这句就省略了
           if(j>=price0+price1){
            dp[i][j]=max(dp[i][j],dp[i-1][j-price0-price1]+price0*priority0+price1*priority1);
           }
           //同理，再买一件2
           if(j>=price0+price2){
            dp[i][j]=max(dp[i][j],dp[i-1][j-price0-price2]+price0*priority0+price2*priority2);
           }
           //类似的，1 2都买
           if(j>=price0+price1+price2){
            dp[i][j]=max(dp[i][j],dp[i-1][j-price0-price1-price2]+price0*priority0+price1*priority1+price2*priority2);
           }
        }
    }
    cout<<dp[m][N]*10<<endl;
}