题解 | 购物单

#include <bits/stdc++.h>
#include <vector>
using namespace std;
struct thing
{
    int v;
    int w;
    int q;
    struct thing* next1;//指向附件1
    struct thing* next2;//指向附件2
};
const int N=32010;
const int M=70;
int f[N];
int main()
{
    int n,m;//预算和物品总数
    cin>>n>>m;
    int V,W,Q;
    vector<thing>things;
    for(int i=0; i<m; i++)
    {
        cin>>V>>W>>Q;
        things.push_back({V,W,Q, nullptr,nullptr});
    }
    for(int i=0; i<m; i++)
    {
        if(things[i].q)//若q为0说明是主件
        {
            int index=things[i].q-1;//因为容器things是从0开始装的，索引要-1
            if(!things[index].next1)//附件1指针为空
                things[index].next1=&things[i];
            else//附件2指针为空
                things[index].next2=&things[i];
        }

    }
     for(int i=0;i<m;i++)
     {
             if(things[i].q==0){
             for(int j=n;j>=things[i].v;j--)
             {
                     //只购买物品i
                     f[j]=max(f[j],f[j-things[i].v]+things[i].w*things[i].v);
                     //主件和配件1
                     if(things[i].next1&&j>=things[i].v+things[i].next1->v)//剩余价格大于主件和一个配件
                     {  auto attv1=(things[i].next1)->v;
                        auto attw1=(things[i].next1)->w;
                        f[j]=max(f[j],f[j-things[i].v-attv1]+things[i].w*things[i].v+attv1*attw1);
                     }
                     //主件和配件2
                     if(things[i].next2&&j>=things[i].v+things[i].next2->v)//剩余价格大于主件和一个配件
                     {  auto attv2=(things[i].next2)->v;
                        auto attw2=(things[i].next2)->w;
                        f[j]=max(f[j],f[j-things[i].v-attv2]+things[i].w*things[i].v+attv2*attw2);
                     }
                     //主件和配件1/2
                     if(things[i].next2&&things[i].next1&&j>=things[i].v+things[i].next2->v+things[i].next1->v)
                     {
                        auto attv1=(things[i].next1)->v;
                        auto attw1=(things[i].next1)->w;
                        auto attv2=(things[i].next2)->v;
                        auto attw2=(things[i].next2)->w;
                        f[j]=max(f[j],f[j-things[i].v-attv1-attv2]+things[i].w*things[i].v+attv1*attw1+attv2*attw2);
                     }
             }
     }
     }
     cout<<f[n]<<endl;
}
// 64 位输出请用 printf("%lld")