题解 | 购物单

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

int main() {
    int buget,num;
    cin>>buget>>num;
    int value,weight,q;
    vector<int>dp(buget,0);
    vector<vector<int>>satisfy(num+1,vector<int>(3,0));
     vector<vector<int>>Value(num+1,vector<int>(3,0));
    for(int i=1;i<=num;i++){
        cin>>value>>weight>>q;
        if(q==0){
            Value[i][0]=value;
            satisfy[i][0]=weight*value;
            if(satisfy[i][1]){
            satisfy[i][1]+=weight*value;
            Value[i][1]+=value;}
            if(satisfy[i][2]){
            satisfy[i][2]+=weight*value;
            satisfy[i][3]+=weight*value;
            Value[i][2]+=value;
            Value[i][3]+=value;}
        }
        else if(q!=0){
            if(satisfy[q][1]==0){
                satisfy[q][1]=weight*value+satisfy[q][0];
                Value[q][1]=value+Value[q][0];
            }
            else{
                satisfy[q][2]=weight*value+satisfy[q][0];
                Value[q][2]=value+Value[q][0];
                satisfy[q][3]=weight*value+satisfy[q][1];
                Value[q][3]=value+Value[q][1];
            }
        }
    }
 for(int j=1;j<=num;j++){
    for(int i=buget;i>=10;i-=10){
       
            if(satisfy[j][0]){
                for(int k=0;k<4;k++){
                if(i>=Value[j][k])
                dp[i]=max(dp[i],satisfy[j][k]+dp[i-Value[j][k]]);}
            }
        }
    }
    cout<<dp[buget]<<endl;
    
}
// 64 位输出请用 printf("%lld")

写的太不容易了这题，好久不写动态规划，绞尽脑汁在想怎么写，最后还是抄抄别人的思路。

首先状态压缩，把附属关系压缩成四种状态：主，主+附1，主+附2，主+附12，一定要考虑到不同的情况，然后就可任意把数据压缩回传统01背包的重量、价值模式。递推公式最好写了，数据不好整理。

第二点的dp数组维度压缩，这点其实我还是想不懂，就背吧。压缩后的遍历顺序，一定是先物品，再背包，并且背包倒序遍历。