博客

题意较好理解：每个主件最多带有两个附件，不超过最大体积（此题为预算价格）的条件下，求最大价值（此题为v*w）

我的想法：主件一个数组，附件一个，装入附件查主件

实施细节：用树的结构把主、附件围在一起，形成了一个分组背包问题，在每一个小组内，都共有2^n（n指附件个数）种选择，即一个主件；一个主分别带

两附件；一个主带两附；

难点：

1.想到用树的结构来组织主件，附件

2.二进制表示不同方案

3.把题目简化为树的结构的抽象模型，抓住主件带附件的抓点

代码有详解

//金明的预算————每个主件带附件的集合中都有2^n种选择，n指附件数量
#include<iostream>
#include<vector>
using namespace std;

const int N = 70,M = 32010;
#define v first
#define w second

typedef pair<int,int> PII;

int n,m;
PII master[N];
vector<PII> servent[N];//与上面不同 这是可以不断增加的
int f[M];

int main()
{
    cin>>m>>n;//钱 物品数量
    for(int i=1;i<=n;i++)
    {
        int v,w,q;
        cin>>v>>w>>q;
        if(!q) master[i]={v,v*w};//加入所有主件
        else servent[q].push_back({v,v*w});//把附件加到对应的主件编号q去
    }
    
    for(int i=1;i<=n;i++)
        if(master[i].v)//只有为主件时才往下走
        {
            for(int j=m;j>=0;j--)
            {
                auto &sv = servent[i];//这里在进行每种主件下每种方案的筛选
                for(int k=0;k< 1<<sv.size();k++)//用二进制表示0，1,2,3
                {
                    int v = master[i].v,w=master[i].w;
                    for(int u=0;u<sv.size();u++)//这里非常巧妙：选一件附件的方案，k=1，转为二进制，不用右移和1进行与运算，正好加入附件中的一个
                        if(k>>u & 1)
                        {
                            v+=sv[u].v;
                            w+=sv[u].w;
                        }
                    if(j>=v) f[j]=max(f[j],f[j-v]+w);
                }
            }
        }
    cout<<f[m];
    return 0;
}