01背包问题的变种

和普通01背包问题不同的是，这一题的物品中有附件，要买附件必须和主件一起买，显然如果想记录每种状态下买了哪些主件是不现实的。

但好在这一题每个主件的附件最多两种，可以分为以下四种状况：
0：只买主件
1：主件+附件1
2：主件+附件2
3：主件+附件1+附件2

因此通过将主件和附件一起考虑，将问题转化为普通的01背包问题。

另外，考虑到物品价格都是10的倍数，处理的时候可以先除10减小空间。
输入数据中物品编号把附件也算进去了，但是后续遍历的时候只需要遍历主件。

代码如下：

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;

int main(){
    int N,m;
    cin>>N>>m;
    N/=10;//价格除10
    vector<int> v(m),p(m),q(m);
    vector<vector<int>> weight(m,vector<int>(4,0));//每种状态的价值
    vector<vector<int>> price(m,vector<int>(4,0));//每种状态的价格
    vector<int> goods;//主物品的序号
    for(int i=0;i<m;i++){
        cin>>v[i]>>p[i]>>q[i];
        v[i]/=10;//价格除10
        if(q[i]==0){
            goods.push_back(i);
            //只算主件
            weight[i][0]=v[i]*p[i];
            price[i][0]=v[i];
        }
    }
    for(int i=0;i<m;i++){
        if(q[i]>0){
            int j=q[i]-1;
            if(weight[j][1]==0){
                //主+附1
                weight[j][1]=weight[j][0]+v[i]*p[i];
                price[j][1]=price[j][0]+v[i];
            }else{
                //主+附2
                weight[j][2]=weight[j][0]+v[i]*p[i];
                //主+附1+附2
                weight[j][3]=weight[j][1]+v[i]*p[i];
                price[j][2]=price[j][0]+v[i];
                price[j][3]=price[j][1]+v[i];
            }
        }
    }
    int num=goods.size();//主物品的数目
    vector<int> dp(N+1,0);
    for(int i=1;i<=num;i++){
        int idx=goods[i];//主件序号
        //dp数组压缩为一维注意价值应从大到小遍历
        for(int j=N;j>=0;j--){
            //考虑每种主件的4种情况
            for(int k=0;k<4;k++){
                if(j>=price[idx][k]){
                    dp[j]=max(dp[j],dp[j-price[idx][k]]+weight[idx][k]);
                }
            }
        }
    }
    //输出价值别忘*10
    cout<<dp[N]*10<<endl;
    return 0;
}