背包问题

weichenglu · 2025-10-21 22:13:48 · 算法·理论

背包问题

背包问题是一个经典的动态规划的问题，大致是给定一个背包的容量与一些物品的重量和价值。要求在物品总重量总和不超过背包容量的前提下，使所得物品总价值最大。

背包问题大致分为以下几种类型：01 背包、完全背包、多重背包、分组背包等。

01 背包

01 背包问题是背包问题中最基础，也是最简单的一类问题。它的主要特点为：对于每个物品，要么选，要么不选。因此被称为 01 背包。

经典问题如下：

有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 v_i，把它放进袋子里会获得 w_i 的收益，每种物品只能用一次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

方法 1——枚举（暴搜）

写一个深搜程序，对 n 个物品分别进行选与不选的枚举（大致代码如下），时间复杂度为 O(2^n)。

int ans = 0;
void dfs(int i,int vsum,int wsum){
    // i -> 搜索到第 i 个物品  vsum,wsum -> 分别为目前已选物品的体积、价值之和
    if (i == n + 1){
        if (vsum <= m) ans = max(ans,wsum);
        return;
    }
    if (v[i] + vsum <= m) dfs(i+1,vsum+v[i],wsum+w[i]); //选
    dfs(i+1,vsum,wsum); // 不选
}

方法 2——

当我们考虑了前 i 个物品选或不选，如果有两组方案的总体积是一样的，那么我们只需要保留总收益大的那组。把考虑了前 i 个物品以后，总体积为 0,1,...,m 时的最大收益都记下来。所以，我们可设 dp_{i,j} 表示考虑前 i 个物品，在背包容量为 j 时，所能获得的最大价值。

考虑前 i 个物品，总体积为 j 时存在两种情况：

不选第 i 个物品，问题就变成了考虑前 i-1 个物品总体积为 j 的情况；
选第 i 个物品，问题就变成了考虑前 i-1 个物品总体积为 j-v_i 的情况。

综上所述：可得状态转移方程式：

dp_{i,j} = \max(dp_{i-1,j},dp_{i-1,j-v_i} + w_i)

写出代码：

int dp[N][M]; //其中N和M分别代表n和m的最大值

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

但是，这样的代码过于复杂，我们可以用以下几个技巧优化，同时，这些技巧是动态规划的常用优化技巧，第一个特别常用！！！

技巧 1——滚动数组

注意到上面代码的空间复杂度为 O(NM)，很明显，在很多题目都会被卡掉，于是，我们需要思考一个问题：需不需要开这么大的数组？

再看到代码，发现考虑前 i 个物品时的状态只和考虑了前 i-1 个物品时的状态有关，所以前面 i-2 行的数据是不用储存的！！！

因此，我们可以使用滚动数组。对于本题，可以使用以下两种方法：

//方法一：

int f[M],g[M];
// f 数组代表前 i-1 个物品的状态
// g 数组代表前 i 个物品的状态

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        if (j < v[i]) g[j] = f[j]; //注意中括号内的变量！！！
        else g[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    memcpy(f,g,sizeof(g)); // 将 g 复制一份给 f
}
cout << f[m]; // 等价于：cout << g[m]

// 方法二：

int dp[2][M];
for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        if (j < v[i]) dp[(i)&1][j] = dp[(i-1)&1][j];
        else dp[i&1][j] = max(dp[(i-1)&1][j],dp[(i-1)&1][j-v[i]]+w[i]);
    }
}
cout << dp[n&1][m];

一般来讲，第二种会更加常用，也更加好用。

技巧 2——逆序滚动数组

先看代码：

int dp[M];
for (int i=1;i<=n;++i){
    for (int j=m;j>=a[i];--j){
        dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }
}

来解释一下原因：（为区分滚动数组优化和逆序滚动数组优化的代码区别，滚动数组优化中的 dp 数组在下文改为 f 数组）

如图，红底和蓝底部分表示目前 dp 数组内，当用二维数组表示时对应的位置。假设现在倒序遍历到蓝底位置，且 v_i 为 2。根据之前的代码，应该算出 f_{i-1,j} 和 f_{i-1,j-v_i} + w_i，在新的代码中却是使用了 dp_j 和 dp_{j-v_i}+w_i，因此，只需判断他们等不等价，就能知道新代码是否正确。

先看 f_{i-1,j} 和 dp_j，因为刚好遍历到 j 为 3 的位置，因此 dp_3 还未更新，所以 dp_3 储存的值不变，也就是等于绿底，为 f_{i-1,3}。所以， f_{i-1,j} 等价于 dp_j。

再看 f_{i-1,j-v_i} + w_i 和 dp_{j-v_i}+w_i，因为 w_i 相同，所以对比 f_{i-1,j-v_i} 和 dp_{j-v_i}。因为 j=3 所以 j-v_i 得到的数一定小于等于 3，即一定在绿底左边的红底的一位置，而这些位置代表的是 f_{i-1,j}，所以 f_{i-1,j-v_i} + w_i 等价于 dp_{j-v_i}+w_i。

综上所述：两段代码等价。（后面的代码基本会也只会使用这种写法）

这样，01背包的状态转移方程式就可以变为（一定要注意，这里是逆序！）

dp_j = \max(dp_j,dp_{j-v_i}+w_i)

模板题

P1048 采药

需要注意的是：这道题目的 n 和 m，是反着输入的！

正确代码：

#include <bits/stdc++.h>
#define N 105
#define M 1005
using namespace std;

int n,m;
int w[105],v[105];
int [1005];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n;
    for (int i=1;i<=n;++i) cin >> w[i] >> v[i];
    for (int i=1;i<=n;++i){
        for (int j=m;j>=w[i];--j){
            [j] = max([j],[j-w[i]]+v[i]);
        }
    }
    cout << [m];

    return 0;
}

完全背包

完全背包是背包问题的另一种问题，区别于01背包，完全背包的特点是：对于每种物品，可以取任意件。

经典问题如下：

有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 v_i，把它放进袋子里会获得 w_i 的收益，每种物品能用无限次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

参考01背包的做法，依旧考虑前 i 种物品，总体积为 j 时存在两种情况：

不选第 i 种物品，问题就变成了考虑前 i-1 种物品总体积为 j 的情况；
选第 i 种物品，问题就变成了考虑前 i 种物品总体积为 j-v_i 的情况。

综上所述：可得状态转移方程式：

dp_{i,j} = \max(dp_{i-1,j},dp_{i,j-v_i}+w_i)

所以，可以写出代码：

int dp[N][M]; 

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

我们对代码进行优化，得到以下代码：

int dp[M]; 

for (int i=1;i<=n;++i){
    for (int j=v[i];j<=m;++j){ // 正序！！！
        dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }
}

可以发现，这段代码与01背包唯一的不同只有第 4 行的循环是正序的。

根据完全背包的定义，每一种物品都可以无限地取，因此如果要选择，我们应该考虑的是前 i 种物品，因为若此时可以选择第 i 种物品，意味着之前也有可能选择过第 i 种物品。要求前 i-1 种物品总值，只需像前面一样即可，因为遍历到 j 这个点时，原来的值还没有被替换掉，因此可以得到 dp_{i-1,j}。而若要求前 i 种物品总值，我们就不能逆序 dp，由于没有更新，所以这样求出的是前 i-1 种物品的总值，如果想要让其在遍历到 dp_j 前更新，就需要先遍历 dp_{j-v_i}，又因为 j-v_i \le j，所以需要正序遍历。

这样，完全背包的状态转移方程式：（一定要注意，这里是正序！）

dp_j = \max(dp_j,dp_{j-v_i}+w_i)

模板题

P1616 疯狂的采药

这道题需要注意两个点：

这道题目的 n 和 m，依旧是反着输入的！
需要使用 long long 类型，否则会爆掉！（代码中使用的是宏定义的形式）

正确代码：

#include <bits/stdc++.h>
#define int long long
#define N 10005
#define M 10000005
using namespace std;

int n,m;
int w[N],v[N];
int [M];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n;
    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){
            [j] = max([j],[j-v[i]]+w[i]);
        }
    }
    cout << [m];    

    return 0;
}

多重背包

多重背包问题是介于 01 背包和完全背包之间的一种问题。它的主要特点是：每种物品有固定的数量限制。

经典问题如下：

有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 v_i，把它放进袋子里会获得 w_i 的收益，每种物品只能不超过 l 次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

方法1：多重背包转 01 背包

由于多重背包问题中，每种物品的数量是固定的，所以，我们可以通过遍历这些数量以求出答案。代码如下：

int dp[M]; 

for (int i=1;i<=n;++i){
    for (int k=1;k<=l[i];++k){// 枚举数量限制
        for (int j=m;j>=v[i];--j){
           dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
}

这段代码得时间复杂度为 O(M \times \sum_{i=1}^{n} l_i)，明显过高。

方法2：二进制优化

为了优化，我们需要用到一个数学结论。首先，先看一下这个结论的简化版：

从 1,2,...,2^m 中选一些数字相加，可以得出任意 [0,2^{m+1}) 内的值，每个数字只能用一次。

这个结论很容易得到，可以用二进制的方法来证明：因为所有数字都为 2 的幂次，所以其二进制都可以用 "1" 加上任意个 "0" 表示，因此可以得出结论。例如：5 = (101)_2 = (100)_2 + (1)_2，13 = (1101)_2 = (1000)_2 + (100)_2 + (1)_2。

因此，对于在 [2^{k+1},2^{k+2}) 内的值，我们取 2^{k+1} 后，剩下的数字在 [0,2^{k+1}) 内，可以从 1,2,...,2^k 中选一些数字相加得到。也就是说任意 [0,2^{k+2}) 内的值可以从 1,2,...,2^{k+1} 中选一些数字相加得到。

设 m=k+1，可以得到对于在 [2^{m+1},n] 内的值，我们取 n-2^{m+1}+1 后，剩下的数字在 [2^{m+2}-n-1,2^{m+1}) 内，可以从 1,2,...,2^m 中选一些数字相加得到。

因此，我们可以枚举 1,2,...,2^k \left(2^k \le m\right) 与 m-2^{k+1}+1，将这个问题转换为 01 背包问题。

代码如下：

int dp[M];

for (int i=1;i<=n;++i){
    int res = l[i];
    for (int k=1;k<=res;res-=k,k*=2) // 二进制拆分
        for (int j=m;j>=v[i]*k;--j) // 01背包
            dp[j] = max(dp[j],dp[j-v[i]*k] + w[i] * k);
    for (int j=m;j>=v[i]*res;--j) // 处理剩余部分
        dp[j] = max(dp[j],dp[j-v[i]*res] + w[i]*res);
}

时间复杂度为 O(M \times \sum_{i=1}^n (\log l_i))。

模板题

P1776 宝物筛选 - 洛谷

正确代码：

#include <bits/stdc++.h>
#define int long long
#define N 105
#define M 40005
using namespace std;

int n,m;
int dp[M];
int v[N],w[N],l[N];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1;i<=n;++i) cin >> w[i] >> v[i] >> l[i];

    for (int i=1;i<=n;++i){
        int res = l[i];
        for (int k=1;k<=res;res-=k,k*=2)
            for (int j=m;j>=v[i]*k;--j)
                dp[j] = max(dp[j],dp[j-v[i]*k] + w[i]*k);
        for (int j=m;j>=v[i]*res;--j)
            dp[j] = max(dp[j],dp[j-v[i]*res] + w[i]*res);
    }
    cout << dp[m];

    return 0;
}

分组背包

分组背包问题是背包问题的一个重要变种，它引入了物品组的概念。它的主要特点是：分组背包中的物品被划分为若干组，对于相同组物品来说，最多只能选择组内的一件物品。

经典问题如下：

有 n 个物品要放到一个袋子里，袋子的总容量为 m，第 i 个物品属于第 a_i 组，体积为 v_i，把它放进袋子里会获得 w_i 的收益，但每组物品只能从中选择一个，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

考虑前 i 组物品选择完以后，把总体积 0,1,...,m 时的最大收益记下来。

考虑前 i 组物品，总体积为 j 时有以下两种情况：

不取第 i 组中的物品，问题就变成了考虑前 i-1 组物品，总体积为 j 时的情况；
取前 i 组中的物品，枚举组中的物品 k，问题就变成了考虑前 i-1 组物品，总体积为 j-v_k 时的情况。

用 c_i 储存在第 i 组中的物品的编号。这样，就可以得到分组背包的状态转移方程式：

dp_{i,j} = \max(dp_{i-1,j},\max_{k \in c_i}(dp_{i-1,j-v_k}+w_k))

代码如下：

for (int i=1;i<=组数;++i){
    for (int j=0;j<=m;++j){
        dp[i][j] = dp[i-1][j];
        for (int k : c[i])
            if (v[k] <= j)
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[k]]+w[k]);
    }
}

接下来，使用滚动数组进行优化，得到代码：

int dp[M];

for (int i=1;i<=组数;++i)
    for (int j=m;j;--j)
        for (int k : c[i]) // 枚举每个组中的物品
            if (v[k] <= j)
                dp[j] = max(dp[j],dp[j-v[k]]+w[k]);

时间复杂度为 O(M \times \sum_{i=1}^{K} c_i)。

模板题

P1757 通天之分组背包 - 洛谷

正确代码：

#include <bits/stdc++.h>
#define ll long long
#define N 1005
#define M 1005
using namespace std;

int n,m;
int v[N],w[N],a[N];
vector<int> c[N];
int dp[M];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n;
    for (int i=1;i<=n;++i){
        cin >> v[i] >> w[i] >> a[i];
        c[a[i]].push_back(i);
    }
    for (int i=1;i<=n;++i){
        for (int j=m;j;--j){
            for (int k : c[i]){
                if (v[k] <= j)
                    dp[j] = max(dp[j],dp[j-v[k]]+w[k]);
            }
        }
    }
    cout << dp[m];

    return 0;
}

二维背包

二维背包是背包问题的重要扩展，它在主要特点是：在01背包的基础上增加了第二个维度的限制。不仅要考虑背包的容量限制，还要考虑另一个资源限制（如重量、体积、时间等）。

经典问题如下：

有 n 种物品要放到一个袋子里，袋子的总容量为 m，一共有 k 点体力值。第 i 种物品的体积为 v_i，把它放进袋子里会获得 w_i 的收益，并且消耗 t_i 点体力值，每种物品只能取一次，问如何选择物品使得在物品的总体积不超过 m 并且花费总体力不超过 k 的情况下，获得最大的收益，请求出最大收益。

这个问题其实很好思考，和01背包的做法一样，考虑前 i 个物品考虑完后，记录总体积为 0,1,...,m 与总体力为 0,1,...,k 时的最大收益。

考虑前 i 组物品，总体积为 j，总体力为 x 时，分为两种情况：

不选第 i 个物品，问题就转换成了考虑前 i-1 个物品，总体积为 j，总体力为 x 时的情况；
选第 i 个物品，问题就转换成了考虑前 i-1 个物品，总体积为 j-v_i，总体力为 x-t_i 时的情况。

这样，就可以得到二维背包的状态转移方程式：

dp_{i,j,x} = \max(dp_{i-1,j,x},dp_{i-1,j-v_i,x-t_i}+w_i)

于是，可以得到代码：

int dp[N][M][K];

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        for (int x=0;x<=k;++x){
            dp[i][j][x] = dp[i-1][j][x];
            if (j >= v[i] && x >= t[i])
                dp[i][j][x] = max(dp[i][j][x],dp[i-1][j-v[i]][x-t[i]]);
        }
    }
}

接下来，使用滚动数组进行优化，得到代码：

int dp[M][K];

for (int i=1;i<=n;++i)
    for (int j=m;j>=v[i];--j) // 类似01背包
        for (int x=k;x>=t[i];--x)
            dp[j][x] = max(dp[j][x],dp[j-v[i]][x-t[i]]+w[i]);

时间复杂度为 O(NMK)。

模板题

P1507 NASA的食物计划

正确代码：

#include <bits/stdc++.h>
#define int long long
#define N 55
#define M 405
#define K 405
using namespace std;

int H,T,n;
int v[N],t[N],w[N];
int dp[M][K];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> H >> T >> n;
    for (int i=1;i<=n;++i) cin >> v[i] >> t[i] >> w[i];

    for (int i=1;i<=n;++i)
        for (int j=H;j>=v[i];--j) // 类似01背包
            for (int x=T;x>=t[i];--x)
                dp[j][x] = max(dp[j][x],dp[j-v[i]][x-t[i]]+w[i]);

    cout << dp[H][T];

    return 0;
}

总结

背包问题是 dp 问题的一种类别，最基础的背包问题是 01 背包和完全背包，在这两种问题的基础上，又扩展出了多重背包、分组背包和二维背包等类别。

以下为各类背包问题的对比图：

问题类型	物品特性	核心代码	时间复杂度
01 背包	每件物品选 0 或 1 次	逆序循环	O(NM)
完全背包	物品无限供应	正序循环	O(NM)
多重背包	每件物品最多选 l_i 次	二进制优化+01背包	O(M \times \sum_{i=1}^n (\log l_i))
分组背包	组内物品互斥	组→容量→组内物品循环	O(M \times \sum_{i=1}^{K} c_i)
二维背包	两个维度限制	双重逆序循环	O(NMK)

其中，二维背包又可以扩展成多维背包，有多个维度的限制，当然，时间复杂度也会增加。

背包问题

背包问题

01 背包

方法 1——枚举（暴搜）

方法 2——

技巧 1——滚动数组

技巧 2——逆序滚动数组

模板题

P1048 采药

完全背包

模板题

P1616 疯狂的采药

推荐题目：

多重背包

方法1：多重背包转 01 背包

方法2：二进制优化

模板题

P1776 宝物筛选 - 洛谷

推荐题目：

分组背包

模板题

P1757 通天之分组背包 - 洛谷

推荐题目：

二维背包

模板题

P1507 NASA的食物计划

推荐题目：

总结