---
url: /algo/5xpcxjf6/index.md
---
# 背包九讲

## 1. 0-1 背包

### 1.1 题目

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的费用是 $v\[i]$，价值是 $w\[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

### 1.2 基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放，接下来就是设计状态，设 $f\[i]\[v]$ 表示选择到第 $i$ 个物品时，背包放入了累计 $v$ 的最大价值。

这样就有状态转移方程：

$$
f\[i]\[v] = \max{f\[i-1]\[v],f\[i-1]\[v-v\[i]]+w\[i]}
$$

::: tip 大白话
每多拿一个物品，就从 $0$ 到 $n$（背包的大小）计算当前大小的背包可以放置的最大价值。将拿这个物品与不拿这个物品的最大价值做比较。若拿这个物品可以增大最大价值，就从没有拿这个物品的且正好有一个可以放这个物体体积的那个值转移过来。若不拿，则直接顺承原来的值。
:::

此类背包本质上就是一个填表游戏，我们来详细看看这个表是怎么被一步步填充的。设有下面几个物品的重量和价值：

::: table title="0-1 背包的示例数据" align="center"
| 编号 | 重量 | 价值 |
| ---- | ---- | ---- |
| 1    | 1   | 5   |
| 2    | 2   | 11  |
| 3    | 3   | 15  |
:::

设背包容量为 $4$，下面是填充表过程：

:::: tabs
@tab 初始

::: center
行标为编号 $i$，列标为背包容量 $c$
:::

::: table align="center"
|      | 0    | 1    | 2    | 3    | 4    |
| ---- | ---- | ---- | ---- | ---- | ---- |
| 0    | 0    | 0    | 0    | 0    | 0    |
| 1    | 0    | 0    | 0    | 0    | 0    |
| 2    | 0    | 0    | 0    | 0    | 0    |
| 3    | 0    | 0    | 0    | 0    | 0    |
:::

@tab 决策第 $1$ 个

::: center
决策第 $1$ 个，表格的变化，紫色表示选取更优，绿色表示装不下必须继承前面的最优解，黄色表示不选取继承更优。
:::

::: table align="center"
|      | 0    | 1    | 2    | 3    | 4    |
| ---- | ---- | ---- | ---- | ---- | ---- |
| 0    | 0    | 0    | 0    | 0    | 0    |
| 1    | 0    | 5 {.important}    | 5 {.important}   | 5 {.important}   | 5 {.important}   |
| 2    | 0    | 0    | 0    | 0    | 0    |
| 3    | 0    | 0    | 0    | 0    | 0    |
:::

@tab 决策第 $2$ 个

::: center
决策第 $2$ 个，表格的变化，紫色表示选取更优，绿色表示装不下必须继承前面的最优解，黄色表示不选取继承更优。
:::

::: table align="center"
|      | 0    | 1    | 2    | 3    | 4    |
| ---- | ---- | ---- | ---- | ---- | ---- |
| 0    | 0    | 0    | 0    | 0    | 0    |
| 1    | 0    | 5    | 5    | 5    | 5    |
| 2    | 0    | 5 {.success}    | 11 {.important}    | 16 {.important}    | 16 {.important}    |
| 3    | 0    | 0    | 0    | 0    | 0    |
:::

@tab 决策第 $3$ 个

::: center
决策第 $3$ 个，表格的变化，紫色表示选取更优，绿色表示装不下必须继承前面的最优解，黄色表示不选取继承更优。
:::

::: table align="center"
|      | 0    | 1    | 2    | 3    | 4    |
| ---- | ---- | ---- | ---- | ---- | ---- |
| 0    | 0    | 0    | 0    | 0    | 0    |
| 1    | 0    | 5    | 5    | 5    | 5    |
| 2    | 0    | 5    | 11    | 16    | 16    |
| 3    | 0    | 5 {.success}    | 11 {.success}    | 16 {.warning}   | 20 {.important}   |
:::

::::

时间复杂度：$O(nm)$

```c++ title="knapsack.cc"
/* 0-1 背包：动态规划 */
int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}
```

### 1.3 优化空间复杂度

思路：这是一个二维 dp 表，但是其实可以理解为是在一直更新某一行。那么我们用一行和背包大小一样大的数组就可以解决了。

```c++
/* 0-1 背包：空间优化后的动态规划 */
int knapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}
```

## 2.完全背包

### 2.1 题目

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

### 2.2 基本思路

这个问题非常类似于 0-1 背包问题，所不同的是每种物品有**无限件**。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……等很多种。如果仍然按照 01 背包的思路，转移方程为：

$$
f\[i]\[v] = \max{f\[i-1]\[v],f\[i]\[v-v\[i-1]]+w\[i-1]}
$$

### 2.3 一维时间优化

整张表的时间复杂度跟 0-1 背包一样是 $O(nm)$，但求每个状态的时间复杂度不再是 $1$，而是 $O(m/v\[i])$，**面临超时问题**

所以为了解决这一问题，我们**改变了转移的顺序**。我们选用一维数组来转移，不再是逆向转移，而是**正向转移**。即两次转移，在转移了没有拿这个物品数组基础上，转移拿了 $k$ 次这个物品的状态。

```c++
int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap)
{
    int n = wgt.size();
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int c = 1; c <= cap; c++)
        {
            if (wgt[i - 1] > c)
            {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            }
            else
            {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}
```

### 2.4 空间优化

由于当前状态是从左边和上边的状态转移而来的，因此空间优化后应该对 $dp$ 表中的每一行进行正序遍历。

```c++
/* 完全背包：空间优化后的动态规划 */
int unboundedKnapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[c] = dp[c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}
```

### 2.4 二进制时间优化

2.3 的时间优化，每个状态都要计算 $m/v\[i]$ 次。但学过二进制的小伙伴都知道，二进制可以降低时间复杂度可以由 $O(V\times\sum v/v\[i])$ 改进到 $O(V\times \sum \log v/v\[i])$。

那也就是说我们可以将其转化为如下所述的多重背包完成，在这里我们暂时不讲如何进行二进制拆包完成。

## 3 多重背包

### 3.1 题目

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $n\[i]$ 件可用，每件容量是 $v\[i]$，价值是 $w\[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

### 3.2 基本思路

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第 $i$ 种物品有 $n\[i]+1$ 种策略：取 $0$ 件，取 $1$ 件……取 $n\[i]$ 件。

令 $f\[i]\[c]$ 表示前 $i$ 种物品恰放入了容量为 $c$ 的背包的最大权值，则：

$$
f\[i]\[c]=\max{f\[i-1]\[c-k\times v\[i]]+k\times w\[i],f\[i-1]\[c]}
$$

$k$ 表示当前物品取的个数，在循环中需要在第三重循环那里加一个个数的限制 `for (int k = 1; k * v[i] <= j && k <=n[i]; k++)`。

```cpp
/* 多重背包：朴素动态规划 */
int multipleKnapsackDP(vector<int> &wgt, vector<int> &val, vector<int> &cnt, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));

    // 遍历物品
    for (int i = 1; i <= n; i++) {
        // 遍历背包容量
        for (int c = 1; c <= cap; c++) {
            // 朴素做法：枚举第 i-1 种物品选择的数量 k
            // 限制条件：1. k 不超过该物品持有数量 cnt[i-1]
            //          2. k 个该物品的总重不超过当前容量 c
            for (int k = 0; k <= cnt[i - 1] && k * wgt[i - 1] <= c; k++) {
                dp[i][c] = max(dp[i][c], dp[i - 1][c - k * wgt[i - 1]] + k * val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}
```

### 3.3.2 二进制时间优化

二进制优化的核心思想是：**任何一个正整数 $cnt$ 都可以拆分为若干个 $2^0, 2^1, 2^2, \dots$ 的组合**。

通过这种拆分，我们可以把“一件件选物品”的过程，变成“一捆捆选物品”的过程。例如：如果你有 7 件相同的物品，你可以把它们打包成三捆，数量分别为 1, 2, 4。通过这三捆的组合，你可以凑出 0 到 7 之间的任何数量。这样，原本需要循环 7 次的**多重背包**就转化为了只需处理 3 个物品的 **0-1 背包**。

由 $O(V\times \sum n\[i])$ 改进到 $O(V\times \sum \log (n\[i]))$ 的过程：

```cpp
/* 多重背包：二进制拆分优化 */
int binMultipleKnapsackDP(vector<int> &wgt, vector<int> &val, vector<int> &cnt, int cap) {
    int n = wgt.size();
    // 用于存储拆分后的新物品
    vector<int> newWgt, newVal;

    // 1. 拆分过程：将多重背包转化为 0-1 背包物品
    for (int i = 0; i < n; i++) {
        int num = cnt[i];
        for (int k = 1; num > 0; k <<= 1) { // k 依次为 1, 2, 4, 8...
            if (num >= k) {
                newWgt.push_back(k * wgt[i]);
                newVal.push_back(k * val[i]);
                num -= k;
            } else {
                // 处理剩余不足 2^n 的部分
                newWgt.push_back(num * wgt[i]);
                newVal.push_back(num * val[i]);
                num = 0;
            }
        }
    }

    // 2. 0-1 背包过程（使用空间优化的滚动数组）
    vector<int> dp(cap + 1, 0);
    for (int i = 0; i < newWgt.size(); i++) {
        // 0-1 背包必须倒序遍历
        for (int c = cap; c >= newWgt[i]; c--) {
            dp[c] = max(dp[c], dp[c - newWgt[i]] + newVal[i]);
        }
    }

    return dp[cap];
}
```

### 3.3.2 单调队列优化

单调队列优化是多重背包的最优解法，它将时间复杂度直接压低到 $O(n \cdot cap)$。

观察状态转移方程：
$$
f\[i]\[c] = \max {f\[i-1]\[c] ,f\[i-1]\[c - k \cdot wgt] + k \cdot val }
$$
其中 $0 \leqslant k \leqslant cnt$。

如果我们令 $c = q \cdot wgt + r$（其中 $r$ 是余数，$0 \leqslant r < wgt$），那么同一个物品在不同的容量下，只有余数 $r$ 相同的状态之间才会相互转换。我们可以按余数 $r$ 分组，利用单调队列维护一个长度为 $cnt+1$ 的滑动窗口最大值。

```cpp
int queueMultipleKnapsackDP(vector<int> &wgt, vector<int> &val, vector<int> &cnt, int cap) {
    int n = wgt.size();
    vector<int> dp(cap + 1, 0);
    vector<int> pre(cap + 1, 0); // 记录上一轮物品的状态

    for (int i = 0; i < n; i++) {
        pre = dp; // 滚动数组备份
        int w = wgt[i];
        int v = val[i];
        int num = cnt[i];

        // 按余数 r 分组，r 范围是 [0, w-1]
        for (int r = 0; r < w; r++) {
            deque<int> dq; // 存储的是下标（即在该余数分组下的第几个物品）
            for (int q = 0; q * w + r <= cap; q++) {
                int curr_c = q * w + r;
                
                // 1. 维护队列单调性：将当前状态值放入队列
                // 我们比较的是去掉“自带价值”后的净值：pre[curr_c] - q * v
                int val_net = pre[curr_c] - q * v;
                while (!dq.empty() && pre[dq.back() * w + r] - dq.back() * v <= val_net) {
                    dq.pop_back();
                }
                dq.push_back(q);

                // 2. 过期出队：如果最前面的下标超出了数量限制 num
                if (dq.front() < q - num) {
                    dq.pop_front();
                }

                // 3. 更新状态：当前最大值 + 这一路补回来的价值
                dp[curr_c] = max(dp[curr_c], pre[dq.front() * w + r] + (q - dq.front()) * v);
            }
        }
    }
    return dp[cap];
}
```

## 4.混合三种背包问题

### 4.1**题目**

如果将P01、P02、P03混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

* si=−1 表示第 i 种物品只能用1次；
* si=0 表示第 i 种物品可以用无限次；
* si>0 表示第 i 种物品可以使用 si 次；

**输出格式**

输出一个整数，表示最大价值。

**数据范围**

0\<N,V≤1000
0\<vi,wi≤1000
−1≤si≤1000

**输入样例**

```
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
```

### 4.2基本思路

三种背包都可以被最终转化为01背包。只能装一次的和用二进制表示后的多重背包逆序传递，完全背包正序传递。

```c++
#include<iostream>
#include<cstring>
#include<algorithm>
using namespacestd; 
int N=1010;
int n,m;
int f[N];
int v,w，s;
struct things{
    int type;
    int v;
    int w;
}
vector<thing> things;
 int main(){
     cin >> n >> m;
     for(int i=1;i<=n;i++){
      cin >> v >> w >>s;
      if(s<0) things.push_back(-1,v,w);
     else if(s==0) thins.push_back(1,v,w);
     else{
         for(int k=1;k<=s;k*=2){
             	s-=k;
             	things.push_back(-1,v*k,w*k);
         	}
         if(s>0) things.push_back(-1,v*s,w*S)
     	}
     }
         for(auto thing:things){
             if(thing.type==1){
              for(int j=thing.v;j<=m;j++)
        	  	f[j]=max(f[j],f[j-thing.v]+thing.w);
             }
             if(thing.type==-1){
              for(int j=m;j>=thing.v;j--)
        	  	f[j]=max(f[j],f[j-thing.v]+thing.w);
             }
         }
     cout << f[m] << endl;
     return 0；
 }
```

## 5.二维费用的背包问题

### 5.1题目

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

**输入格式**

第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

**输出格式**

输出一个整数，表示最大价值。

**数据范围**

0\<N≤1000
0\<V,M≤100
0\<vi,mi≤100
0\<wi≤1000

**输入样例**

```
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
```

**输出样例**

```
8
```

### 5.2基本思路

将压缩以后的一维数组变成二维数组

```c++
#include<iostream>
#include<cstring>
#include<algorithm>
using namespacestd; 
int N=1010;
int main（）{
int n,m,d;
int f[N][N];
int v,w,h;
 int main(){
     cin >> n >> m >> d;
     for(int i=1;i<=n;i++)
      cin >> v >> w >> h;
         for(int j=m;j>=v;j--){
             for(int k=d;k>=h;k--){
                 f[j][k]=max(f[j][k],f[j-v][k-h]+w);}
     cout << f[m][d] << endl;
 }
 }
```

## 6.分组背包问题

### 6.1题目

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

**输入格式**

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

* 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
* 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

**输出格式**

输出一个整数，表示最大价值。

**数据范围**

0\<N,V≤100
0\<Si≤100
0\<vij,wij≤100

**输入样例**

```
3 5
2
1 2
2 4
1
3 4
1
4 5
```

**输出样例**

```
8
```

### 6.2基本思路

将每一组背包看作是dp表中的一行，再在一行里用组里面的每个物品去求解那个最优结果。

```c++
#include<iostream>
#include<cstring>
#include<algorithm>
using namespacestd; 
int N=1010;
int main（）{
int n,m,d;
int f[N];
int v[N],w[N];
 int main(){
     cin >> n >> m;
     for(int i=1;i<=n;i++){
      int num;
      cin >> num;
      for(int j=1;j<=num;j++){
      		cin >> v[j] >> w[j];
       }
       for(int j=m;j>=0;j--){
           for(int k=1;k<=num&&v[k]<=j;k++){
               f[j]=max(f[j],f[j-v[k]]+w[k]);
           }
     }
     }
     cout << f[m]<< endl;
 }
```

## 7.依赖的背包问题(树上背包)

### 6.1题目

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

**输入格式**

第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 **数据保证所有物品构成一棵树。**

**输出格式**

输出一个整数，表示最大价值。

**输入样例**

```
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
```

**输出样例**

```
11
```

### 6.2基本思路

​	这道题可以理解成一个plus版本的分组背包，假设有b1,b2,b3...个背包都是a背包的父节点（选择bi中任意个背包都要选上a）。此时我们有不选a，选a再选b1，选a再选b1，b2，选a再选b1，b2，b3等2^i^+1种选法。将其看作分组背包的话，也就是每组里面有2^i^+1个物品，每个背包里的物品的体积和价值即是所选背包的和。
但是指数级别的时间复杂度无疑是消受不起的。

我们称a为主件，bi为附件组。

这是我们怎么减少选法呢？我们选择使用01背包的方式，把附件组的选择**看作是用v-c\[i]容量的背包在i个物品里里面选择最大价值**。这样就可以减少成了v-c【i】+1种选法。

```c++
#include<iostream>
using namespace std;
const int N = 100010;

int n, m;
int h[N],e[N],ne[N],idx;
int v[N], w[N], f[N][N];
void add(int a, int b) {
	e[idx] = b, //当前边指向的子节点是b
	ne[idx] = h[a],//当前边的下一条边是原来a的第一条边
	h[a] = idx++;//跟新a的第一条边为当前边
}

void dfs(int u)
{
	for (int i = h[u];i!=-1;i=ne[i]) {
		int son = e[i];
		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);
	}

	dfs(root);
	cout << f[root][m] << endl;

	return 0;
}
```