背包系列问题

发表于 2020-11-14 更新于 2023-11-05 分类于与算法的每日Battle 阅读次数：本文字数： 15k 阅读时长 ≈ 14 分钟

背包问题算法模板题目集合，涵盖了所有类型的背包问题。

背包系列问题

以下问题的题目均采用AcWing题库

01背包问题

问题描述（AcWing-2）

有 $N$ 件物品和一个容量为 $V$ 的背包。放入第 $i$ 件物品耗费的费用是 $C_i$ ，得到的价值是 $W_i$ 。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即 $F[i, v]$ 表示前 $i$ 件物品恰放入一个容量为 $v$ 的背包可以获得的最大价值。则其状态转移方程便是：

$F[i, v] = max\{F[i - 1, v], F[i - 1, v - C_i ] + W_i \}$

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：

“将前 $i$ 件物品放入容量为 $v$ 的背包中‘’这个子问题，若只考虑第 $i$ 件物品的策略（放或不放），那么就可以转化为一个只和前 $i - 1$ 件物品相关的问题。

如果不放第 $i$ 件物品，那么问题就转化为“前 $i - 1$ 件物品放入容量为 $v$ 的背包中”，价值为 $F[i - 1, v]$ ；

如果放第 $i$ 件物品，那么问题就转化为“前 $i - 1$ 件物品放入剩下的容量为 $v - C_i$ 的背包中”，此时能获得的最大价值就是 $F[i - 1, v - C_i ]$ 再加上通过放入第 $i$ 件物品获得的价值 $W_i$ 。

伪代码如下：

F[0, 0 ... V] = 0
for i from 1 to N
	for v from Ci to V
		F[i,v] = max{F[i - 1, v], F[i - 1, v - Ci] + Wi}

AcWing-2 解答

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

int compute(int n, int space, vector<pair<int, int>>& prods){
    int m[n + 1][space + 1];
    memset(m, 0, sizeof(m));
	  int i = 0, j = 0;
	  for(i = 1; i <= n; i++){
		    for(j = 1; j <= space; ++j){
			      m[i][j] = m[i - 1][j];
			      if(j >= prods[i].first){
				        m[i][j] = max(m[i - 1][j], m[i - 1][j - prods[i].first] + prods[i].second);
			      }
		    }
	  }
	  return m[i - 1][j - 1];
}

int main(){
    int n, space;
    cin >> n >> space;
    vector<pair<int, int>> prods;
    prods.push_back({0, 0});
    for(int i = 0; i < n; ++i){
        int vi, wi;
        cin >> vi >> wi;
        prods.push_back({vi, wi});
    }
    cout << compute(n, space, prods) << endl;
    return 0;
}

优化空间复杂度

以上方法的时间和空间复杂度均为 $O(V N)$ ，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 $O(V )$ 。

只用一个数组 $F[0 . . . V ]$ ，第 $i$ 次循环结束后 $F[v]$ 中表示的就是我们之前定义的状态 $F[i, v]$

$F[i, v]$ 是由 $F[i - 1, v]$ 和 $F[i - 1, v - C_i ]$ 两个子问题递推而来，我们只需要在每次主循环中我们以 $v ← V . . . 0$ 的递减顺序计算 $F[v]$ ，即可保证计算 $F[v]$ 时 $F[v - C_i ]$ 保存的是状态 $F[i - 1, v - C_i]$ 的值。

伪代码如下：

F[0 ... V] = 0
for i from 1 to N
	for v from V to Ci
		F[v] = max{F[v], F[v - Ci] + Wi}

AcWing-2 优化解答

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

int compute(int n, int space, vector<pair<int, int>>& prods){
    int m[space + 1];
    memset(m, 0, sizeof(m));
    for(int i = 1; i <= n; i++){
        for(int j = space; j >= prods[i].first; --j){
            if(j >= prods[i].first){
              	m[j] = max(m[j], m[j - prods[i].first] + prods[i].second);
            }
        }
    }
    return m[space];
}

int main(){
    int n, space;
    cin >> n >> space;
    vector<pair<int, int>> prods;
    prods.push_back({0, 0});
    for(int i = 0; i < n; ++i){
        int vi, wi;
        cin >> vi >> wi;
        prods.push_back({vi, wi});
    }
    cout << compute(n, space, prods) << endl;
    return 0;
}

初始化的细节问题

“恰好装满背包”：在初始化时除了 $F[0]$ 为 $0$ ，其它 $F[1..V]$ 均设为 $-∞$ ，这样就可以保证最终得到的 $F[V]$ 是一种恰好装满背包的最优解;
“不要求恰好装满背包”：将 $F[0..V]$ 全部设为 $0$ 。

初始化的 $F$ 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 $0$ 的背包可以在什么也不装且价值为 $0$ 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 $-∞$ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 $0$ ，所以初始时状态的值也就全部为 $0$ 了。

完全背包问题

问题描述（AcWing-3）

有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品都有无限件可用。放入第 $i$ 种物品的费用是 $C_i$ ，价值是 $W_i$ 。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……直至取 $⌊V / C_i⌋$ 件等许多种。

如果仍然按照解 01 背包时的思路，令 $F[i, v]$ 表示前 $i$ 种物品恰放入一个容量为 $v$ 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

$F[i, v] = max\{F[i - 1, v - kC_i ] + kW_i | 0 ≤ kC_i ≤ v\}$

这跟 01 背包问题一样有 $O(V N)$ 个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态 $F[i, v]$ 的时间是 $O(\frac{V}{C_i})$ ，总的复杂度可以认为是 $O(NV \sum \frac{V}{C_i})$ ，是比较大的。

将 01 背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明 01 背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是要试图改进这个复杂度。

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin >> v[i] >> w[i];
    }

    for(int i = 1 ; i <= n ;i++)
    for(int j = 0 ; j <= m ;j++)
    {
        for(int k = 0; k * v[i] <= j; k++)
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    }

    cout<<f[n][m]<<endl;
}

简单有效的优化

完全背包问题有一个很简单有效的优化，是这样的：若两件物品 $i$ 、 $j$ 满足 $C_i ≤ C_j$ 且 $W_i ≥ W_j$ ，则将可以将物品 $j$ 直接去掉，不用考虑。

这个优化的正确性是显然的：任何情况下都可将价值小费用高的 $j$ 换成物美价廉的 $i$ ，得到的方案至少不会更差。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。

这个优化可以简单的 $O(N^2)$ 地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于 $V$ 的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以 $O(V + N)$ 地完成这个优化。

转化为01背包问题求解(可参考)

01 背包问题是最基本的背包问题，我们可以考虑把完全背包问题转化为 01 背包问题来解。

最简单的想法是，考虑到第 $i$ 种物品最多选 $⌊V /C_i ⌋$ 件，于是可以把第 $i$ 种物品转化为 $⌊V /C_i ⌋$ 件费用及价值均不变的物品，然后求解这个 01 背包问题。这样的做法完全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为 01 背包问题的思路：将一种物品拆成多件只能选 0 件或 1 件的 01 背包中的物品。

更高效的转化方法是：把第 $i$ 种物品拆成费用为 $C_i 2^k$ 、价值为 $W_i 2^k$ 的若干件物品，其中 $k$ 取遍满足 $C_i 2^k ≤ V$ 的非负整数。

这是二进制的思想。因为，不管最优策略选几件第 $i$ 种物品，其件数写成二进制后，总可以表示成若干个 $2^k$ 件物品的和。这样一来就把每种物品拆成 $O(log ⌊V /C_i ⌋)$ 件物品，是一个很大的改进。

O(VN) 算法

这个算法使用一维数组，先看伪代码：

F[0..V] = 0 
	for i from 1 to N
		for v from Ci to V
			F[v] = max(F[v], F[v − Ci] + Wi)

这个伪代码与 01 背包问题的伪代码只有 $v$ 的循环次序不同而已。

为什么这个算法就可行呢？首先想想为什么 01 背包中要按照 $v$ 递减的次序来循环。让 $v$ 递减是为了保证第 $i$ 次循环中的状态 $F[i, v]$ 是由状态 $F[i - 1, v - C_i ]$ 递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 $i$ 件物品”这件策略时，依据的是一个绝无已经选入第 $i$ 件物品的子结果 $F[i - 1, v - C_i]$ 。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 $i$ 种物品”这种策略时，却正需要一个可能已选入第 $i$ 种物品的子结果 $F[i, v - C_i]$ ，所以就可以并且必须采用 $v$ 递增的顺序循环。这就是这个简单的程序为何成立的道理。

值得一提的是，上面的伪代码中两层 for 循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。

这个算法也可以由另外的思路得出。例如，将基本思路中求解 $F[i, v - C_i]$ 的状态转移方程显式地写出来，代入原方程中，会发现该方程可以等价地变形成这种形式：

$F[i, v] = max(F[i - 1, v], F[i, v - C_i] + W_i)$

将这个方程用一维数组实现，便得到了上面的伪代码。最后抽象出处理一件完全背包类物品的过程伪代码：

1
2
3

def CompletePack(F, C, W)
	for v ← C to V
		F[v] ← max{F[v], f[v − C] + W}

细节说明

我们列举一下更新次序的内部关系：

f[i , j ] = max(f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(           f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-2*v]+2*w , .....)
由上两式，可得出如下递推关系： 
              f[i][j] = max(f[i,j-v]+w , f[i-1][j])

有了上面的关系，那么其实k循环可以不要了，核心代码优化成这样：

for(int i = 1 ; i <= n ;i++)
for(int j = 0 ; j <= m ;j++)
{
    f[i][j] = f[i - 1][j];
    if((j-v[i] >= 0)
        f[i][j]=max(f[i][j],f[i][j - v[i]] + w[i]);
}

这个代码和01背包的非优化写法很像

我们对比一下，下面是01背包的核心代码

for(int i = 1 ; i <= n ; i++)
for(int j = 0 ; j <= m ; j ++)
{
    f[i][j] = f[i - 1][j];
    if(j - v[i] >= 0)
        f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);
}

两个代码其实只有一句不同（注意下标）

1 2	f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包 f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

因为和01背包代码很相像，我们很容易想到进一步优化。核心代码可以改成下面这样

for(int i = 1 ; i<=n ;i++)
   for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
   {
       f[j] = max(f[j],f[j-v[i]]+w[i]);
   }

综上所述，完全背包的最终写法如下：

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin >> v[i] >> w[i];
    }
    for(int i = 1; i <= n; i++)
    for(int j = v[i]; j <= m; j++)
    {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    cout << f[m] << endl;
}

多重背包问题

问题描述（AcWing-4）

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $M_i$ 件可用，每件耗费的空间是 $C_i$ ，价值是 $W_i$ 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

基本算法

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。

因为对于第 $i$ 种物品有 $M_i + 1$ 种策略：取 0 件，取 1 件……取 $M_i$ 件。令 $F[i, v]$ 表示前 $i$ 种物品恰放入一个容量为 $v$ 的背包的最大价值，则有状态转移方程：

$F[i, v] = max\{F[i - 1, v - k * C_i ] + k * W_i | 0 ≤ k ≤ M_i\}$

复杂度是 $O(V \sum {M_i})$ 。

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;

int v[N], w[N], s[N];
int f[N][N];
int n, m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];

    for(int i = 1; i <= n; i ++){//枚举背包
        for(int j = 1; j <= m; j ++){//枚举体积
            for(int k = 0; k <= s[i]; k ++){
                if(j >=  k * v[i]){
                    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
    }

    cout << f[n][m] << endl;
    return 0;
}

转化为 01 背包问题

另一种基本方法是转化为 01 背包求解：把第 $i$ 种物品换成 $M_i$ 件 01 背包中的物品，则得到了物品数为 $\sum M_i$ 的 01 背包问题。直接求解之，复杂度仍然是 $O(V \sum M_i )$ 。

但是我们期望将它转化为 01 背包问题之后，能够像完全背包一样降低复杂度。

仍然考虑二进制的思想，我们考虑把第 $i$ 种物品换成若干件物品，使得原问题中第 $i$ 种物品可取的每种策略——取 $0 . . . M_i$ 件——均能等价于取若干件代换以后的物品。另外，取超过 $M_i$ 件的策略必不能出现。

方法是：将第 $i$ 种物品分成若干件 01 背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为 $1, 2, 2^2 . . . 2^{k-1} , M_i - 2^k + 1$ ，且 $k$ 是满足 $M_i - 2^k + 1 > 0$ 的最大整数。例如，如果 $M_i$ 为 13，则相应的 $k = 3$ ，这种最多取 13 件的物品应被分成系数分别为 1, 2, 4, 6 的四件物品。

分成的这几件物品的系数和为 $M_i$ ，表明不可能取多于 $M_i$ 件的第 $i$ 种物品。另外这种方法也能保证对于 $0 . . . M_i$ 间的每一个整数，均可以用若干个系数的和表示。这里算法正确性的证明可以分 $0 . . . 2^{k-1}$ 和 $2^k . . . M_i$ 两段来分别讨论得出。

这样就将第 $i$ 种物品分成了 $O(logM_i)$ 种物品，将原问题转化为了复杂度为 $O(V \sum logM_i)$ 的 01 背包问题，是很大的改进。下面给出 $O(logM)$ 时间处理一件多重背包中物品的过程：

def MultiplePack(F, C, W, M)
	if C · M ≥ V 
		CompletePack(F, C, W) 
		return 
	k ← 1
	while k < M
		ZeroOnePack(kC, kW)
		M ← M − k
		k ← 2k
	ZeroOnePack(C·M, W·M)

O(VN) 算法

当问题是“每种有若干件的物品能否填满给定容量的背包”，只须考虑填满背包的可行性，不需考虑每件物品的价值时，多重背包问题同样有 O(VN) 复杂度的算法。

例如，可以使用单调队列的数据结构，优化基本算法的状态转移方程，使每个状态的值可以以均摊 $O(1)$ 的时间求解。

下面介绍一种实现较为简单的 $O(V N)$ 复杂度解多重背包问题的算法。它的基本思想是这样的：设 $F[i, j]$ 表示“用了前 $i$ 种物品填满容量为 $j$ 的背包后，最多还剩下几个第 $i$ 种物品可用”，如果 $F[i, j] = -1$ 则说明这种状态不可行，若可行应满足 $0 ≤ F[i, j] ≤ M_i$ 。

递推求 $F[i, j]$ 的伪代码如下：

F[0, 1 . . . V ] ← −1 
F[0, 0] ← 0
for i ← 1 to N
	for j ← 0 to V
		if F[i − 1][j] ≥ 0
			F[i][j] = Mi
		else
			F[i][j] = −1
	for j ← 0 to V − Ci
		if F[i][j] > 0
			F[i][j + Ci] ← max{F[i][j + Ci], F[i][j] − 1}

最终 $F[N][0 . . . V]$ 便是多重背包可行性问题的答案。

混合背包问题

问题描述（AcWing-7）

将以上三个问题混合起来，即有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取有限次（多重背包）。

基本思路

考虑到01背包和完全背包伪代码只有一处不同，故如果只有两类物品，一类物品只能取一次，另一类物品可以取无限次，那么只需在每个物品应用转移方程时，根据物品的类别选用顺序或逆序循环即可。复杂度 $O(VN)$ 。
对于多重背包式的物品，利用单调队列，也可以给出均摊复杂度 $O(VN)$ 的解法。

问题分类拆分解法

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

struct Good {
    int v;
    int w;
};

int zeroOnePack(int n, int m, const vector<Good>& goods) {
    vector<int> dp(m + 1, 0);
    for (const auto& good : goods) {
        for (int j = m; j >= good.v; j--) {
            dp[j] = max(dp[j], dp[j - good.v] + good.w);
        }
    }

    return dp[m];
}

int main()
{
    int t = 1, n, m, wi, vi, s;
    cin >> n >> m;
    vector<Good> goods;
    while(n--) {
        cin >> vi >> wi >> s;
        int k;
        // Break multiple knapsack into 0-1 knapsack using binary split
        auto binarySplitToZeroOne = [&]() {
         for (k = 1; k <= s; k <<= 1) {
                 goods.push_back({k * vi, k * wi});
                 s -= k;
            }
            if (s > 0) {
                goods.push_back({s * vi, s * wi});
            }
        };
        if (s > 0) { // Multiple knapsack
            binarySplitToZeroOne();  
        } else if (s == 0) { // Complete knapsack
            s = m / vi; // convert to multiple knapsack
            binarySplitToZeroOne();
        } else if (s == -1) { // zero one knapsack
            goods.push_back({vi, wi});
        }
    }

    auto res = zeroOnePack(n, m, goods);
    cout << res <<endl;

    return 0;
}

二维费用背包问题

问题描述（AcWing-8）

对于每件物品，具有两种不同的费用，例如重量和空间。

基本思路

费用增加了一维，只需状态也增加一维即可。设 $F[i,v,u]$ 表示前 $i$ 件物品付出两种费用分别为 $v$ 和 $u$ 时可获得的最大价值。状态转移方程为：

$F[i,v,u] = max\{F[i-1,v,u],F[i-1,v-C_i,u-D_i]+W_i \}$

根据01背包问题的状态压缩优化思路，可以只使用二维的数组，当每件物品只可以取一次时，变量 $v$ 和 $u$ 采用逆序的循环。

当物品有如完全背包问题时采用顺序的循环，当物品有如多重背包问题时拆分物品。

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

int n, V, M;
const int N = 1e3 + 5;
int v[N], m[N], w[N], f[N][N];

int main () {
    cin >> n >> V >> M;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i] >> m[i] >> w[i];//体积，重量，价值
    }
    for (int i = 1; i <= n; i ++)
        for (int j = V; j >= v[i]; j --)
            for (int k = M; k >= m[i]; k --)
                f[j][k] = max (f[j - v[i]][k - m[i]] + w[i], f[j][k]);
    cout << f[V][M];
  	return 0;
}

物品总个数的限制

有时，“二维费用”的条件为：最多只能取 $U$ 件物品，这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为 $U$ 。换句话说，设 $F[v,u]$ 表示付出费用 $v$ 、最多选 $u$ 件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在 $F[0...V,0...U]$ 范围内寻找答案。

分组背包问题

问题描述（AcWing-9）

物品别划分为 $K$ 组，每组中的物品互相冲突，最多选一件。

基本思路

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设 $F[k,v]$ 表示前 $k$ 组物品花费费用 $v$ 能取得的最大权值，则有：

$F[k,v]=max\{ F[k-1,v],F[k-1,v-C_i]+W_i|item_i \in group_k \}$

使用一维数组的伪代码如下：

for k ← 1 to k
	for v ← V to 0
		for all item i in group k
			F[v] ← max{F[v], F[v - C_i] + W_i}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N],v[N][N],w[N][N],s[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++)
            cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            for(int k=0;k<s[i];k++)
                if(v[i][k]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
        }
    }
    cout<<f[n][m];
    return 0;
}

使用同01背包一样优化思路

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N],v[N][N],w[N][N],s[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++)
            cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<s[i];k++)
                if(v[i][k]<=j) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }
    }
    cout<<f[m];
    return 0;
}

有依赖的背包问题

问题描述（AcWing-10）

物品间存在某种“依赖”关系，即物品 $i$ 依赖于物品 $j$ ，表示若选物品 $i$ ，则必须选物品 $j$ 。为了简化起见，设没有某个物品既依赖于别的物品，又被别的物品所依赖，另外，没有某件物品同时依赖多件物品。

基本思路

把有依赖的背包问题看成是分组背包问题，每一个结点是看成是分组背包问题中的一个组，子节点的每一种选择我们都看作是组内的一种物品，因此我们可以通过分组背包的思想去写。
但它的难点在于如何去遍历子节点的每一种选择，即组内的物品，我们的做法是从叶子结点开始往根节点做，并使用数组表示的邻接表来存贮每个结点的父子关系。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 110;
int n,m;
int h[N],e[N],ne[N],idx;
/*h数组是邻接表的头它的下表是当前节点的标号，值是当前结点第一条边的编号（其实是最后加入的那一条边），e数组是边的集合，它的下标是当前边的编号，数值是当前边的终点；
ne是nextedge，如果ne是-1表示当前结点没有下一条边，ne的下标是当前边的编号，数值是当前结点的下一条边的编号，idx用于保存每一条边的上一条边的编号。
这样我们就知道了当前结点的第一条边是几，这个边的终点是那个结点，该节点的下一条边编号是几，那么邻接表就完成了
*/ 
int v[N],w[N],f[N][N]; 

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;//该方法同于向有向图中加入一条边，这条边的起点是a，终点是b，加入的这条边编号为idx 
}

void dfs(int u){
    for(int i = h[u];i!=-1;i = ne[i]){//对当前结点的边进行遍历 
        int son = e[i];//e数组的值是当前边的终点，即儿子结点 
        dfs(son); 
        for(int j = m-v[u];j>=0;j--){
        //遍历背包的容积，因为我们是要遍历其子节点，所以当前节点我们是默认选择的。
        //这个时候当前结点我们看成是分组背包中的一个组，子节点的每一种选择我们都看作是组内一种物品，所以是从大到小遍历。
        //我们每一次都默认选择当前结点，因为到最后根节点是必选的。 
            for(int k = 0;k<=j;k++){//去遍历子节点的组合 
                f[u][j] = max(f[u][j],f[u][j-k]+f[son][k]);
            }
        }
    }
    //加上刚刚默认选择的父节点价值
    for(int i = m;i>=v[u];i--){
        f[u][i] = f[u][i-v[u]]+w[u];
    }
    //因为我们是从叶子结点开始往上做，所以如果背包容积不如当前物品的体积大，那就不能选择当前结点及其子节点，因此赋值为零 
    for(int i = 0;i<v[u];i++){
        f[u][i] = 0;
    }
}

int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int root;
    for(int i = 1;i<=n;i++){
        int p;
        cin>>v[i]>>w[i]>>p;
        if(p==-1){
            root = i;
        }else{
            add(p,i);//如果不是根节点就加入邻接表,其中p是该节点的父节点，i是当前是第几个节点
        }
    }
    dfs(root);
    cout<<f[root][m]<<endl;
    return 0;
}

背包系列问题

01背包问题

问题描述（AcWing-2）

基本思路

优化空间复杂度

初始化的细节问题

完全背包问题

问题描述（AcWing-3）

基本思路

简单有效的优化

转化为01背包问题求解(可参考)

O(VN)​ 算法

细节说明

多重背包问题

问题描述（AcWing-4）

基本算法

转化为 01 背包问题

O(VN) 算法

混合背包问题

问题描述（AcWing-7）

基本思路

问题分类拆分解法

二维费用背包问题

问题描述（AcWing-8）

基本思路

物品总个数的限制

分组背包问题

问题描述（AcWing-9）

基本思路

有依赖的背包问题

问题描述（AcWing-10）

基本思路

O(VN) 算法