历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 487. 金明的预算方案【有依赖背包DP+分组背包集合划分】原题链接中等

作者：

一只野生彩色铅笔 , 2021-06-29 11:20:19 , 所有人可见 , 阅读 4443

39

8

最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

一共有 $N$ 个物品和 $M$ 元钱

物品之间可能存在 依赖关系，对于第 $i$ 个物品，价格为 $v_i$，价值为 $w_i$，依赖的父物品为 $p_i$

每个物品只能被购买一次

依赖关系：只有购买了父物品后，才能购买子物品（若 $p_i=0$ 表示该物品为主件）

求一种 购买方案，使得 总花费 不超过 $M$，且 总价值 最大

分析

本题是一道 背包DP 的 经典变种题目：有依赖的背包 DP

根据题设的 拓扑结构 可以观察出每个物品的关系构成了森林

而以往的 背包DP 每个物品关系是 任意的（但我们一般视为 线性的）

所以，这题沿用 背包DP 的话，要从原来的 线性DP 改成 树形DP 即可

在有依赖的背包问题【有依赖背包DP+子物品体积集合划分】中我们利用了子物品的体积进行 集合划分

时间复杂度是 $O(N \times V \times V)$

但是对于本题 $V$ 的数据范围是 $3.2 \times 10^4$，如果用该种集合 划分方案，毫无疑问会超时

注意到题目中有提到，每个主件的 附属品 数量不超过 $2$ 个，且 附物品 不会再有 附属品

因此我们可以采用 分组背包 对本题的状态进行 集合划分

具体思路就是，枚举所有选 子物品 的组合，每一个组合对应一个分组背包中的物品

这样时间复杂度是 $O(N \times 2^2 \times V)$

闫氏DP分析法：

$f(i,j)$状态表示—集合：考虑前 $i$ 个背包组，且总体积不超过 $j$ 的方案

$f(i,j)$状态表示—属性：方案的总价值 最大MAX

$f(i,j)$状态计算：
$$ f(i,j) = \max\bigg(f(i-1,j), \max\Big(f(i-1,j-v_k)+w_k\Big)\bigg) \quad 其中k是枚举的物品组i中的物品 $$

Code

时间复杂度: $O(N \times 2^2 \times V)$

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 65, M = 32010;

int n, m;
int w[N], v[N], f[M];
bool not_aff[N];//标记每个分组背包
vector<int> aff[N];//存储每个分组背包内的物品

//dp
void dp(int u, int j)
{
    int siz = aff[u].size();
    //二进制枚举，列举出所有的分组背包内的物品
    for (int st = 0; st < 1 << siz; ++ st)
    {
        int v_sum = v[u], w_sum = w[u];//必须购买主键后，附件才有价值
        for (int i = 0; i < siz; ++ i)
        {
            if (st >> i & 1)
            {
                v_sum += v[aff[u][i]];
                w_sum += w[aff[u][i]];
            }
        }
        //状态转移
        if (v_sum <= j) f[j] = max(f[j], f[j - v_sum] + w_sum);
    }
}
int main()
{
    //input
    cin >> m >> n;
    for (int i = 1; i <= n; ++ i)
    {
        int fa;
        cin >> v[i] >> w[i] >> fa;
        w[i] *= v[i];
        if (fa) aff[fa].push_back(i);
        else not_aff[i] = true;//标记分组背包的物品组
    }
    //dp
    for (int i = 1; i <= n; ++ i)
        if (not_aff[i]) //分组背包
            for (int j = m; j >= 0; -- j)
                dp(i, j);
    //output
    cout << f[m] << endl;
    return 0;
}

15 评论

人生何处不青山 2021-09-16 09:15

请问可以不选主键吗

一只野生彩色铅笔 2021-09-16 09:23

题目里不是说购买附件必须先选主件吗QAQ

人生何处不青山 2021-09-16 09:25 回复了一只野生彩色铅笔的评论

是但是可不可以附件主件都不买QAQ

一只野生彩色铅笔 2021-09-16 09:30 回复了人生何处不青山的评论

可以呀，这里状态转移规则用的是01背包的
如果同体积下，价值没有比原来更大，则不会更新

人生何处不青山 2021-09-16 09:31 回复了一只野生彩色铅笔的评论

好的大佬tql

福贵 2022-08-12 08:58

nice

改了吧 2022-05-08 17:33

按照大佬的思路写了个二维dp，但是有一个数据过不了，大佬们能看看吗
（主要就是改了体积的循环顺序和状态转移方程部分）

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=70,M=32010;
#define x first
#define y second
int f[N][M];
vector<PII> servant[N];
PII master[N];

int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int v,w,q;
        cin>>v>>w>>q;
        if(q==0)
        {
            master[i]=make_pair(v,w*v);
        }
        else
        {
            servant[q].push_back(make_pair(v,w*v));
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int maxv=-1;
            for(int k=0;k<(1<<servant[i].size());k++)//一个都不选到所有都考虑
            // 00 01 10 11共4种到0~3
            {
                int v=master[i].x,w=master[i].y;
                for(int a=0;a<servant[i].size();a++)
                {
                    if(k>>a&1)//k第a位等于1
                    //这里附件最多两件所以选法最多 00 01 10 11 四种
                    {
                        v+=servant[i][a].x;
                        w+=servant[i][a].y;
                    }
                }

                if(j>=v)//不选第i个物品组和选第i个物品组的各种情况
                {
                    maxv=max(maxv,f[i-1][j-v]+w);
                    f[i][j]=max(f[i-1][j],maxv);//当前选到编号i件主件总体积为j选 第k种选法的最大价值
                }
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

shangfei 2023-10-02 09:47

#include <bits/stdc++.h>
using namespace std;

const int N = 70, M = 320010;
typedef pair<int, int> PII;
PII master[N];
vector<PII> servent[N];
int f[N][M];


int main()
{
    int n, m;
    cin >> m >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        int v, p, q;
        cin >> v >> p >> q;
        p = v * p;
        if(q == 0)
            master[i] = {v, p};
        else
            servent[q].push_back({v, p});
    }

    for(int i = 1 ; i <= n ; i++)
        for(int j = m ; j >= 0 ; j--)
        {
            f[i][j] = f[i-1][j]; //放在外层，代表不选第i个物品
            for(int k = 0 ; k < 1 << servent[i].size() ; k++)
            {
                int v = master[i].first, p = master[i].second;
                for(int u = 0 ; u < servent[i].size() ; u++)
                {
                    if((k >> u) & 1)
                    {
                        v += servent[i][u].first;
                        p += servent[i][u].second;
                    }
                }
                if(j >= v) f[i][j] = max(f[i][j], f[i-1][j-v] + p);
            }
        }
    cout << f[n][m] << endl;
    return 0;
}