【动态规划】背包问题详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】背包问题详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划（Dynamic Pogramming，简称dp）是运筹学的一个分支，是求解决策过程最优化的数学方法。背包问题则是dp问题里很常见的一类。本篇文章来详解一下背包问题。

1、基础知识

动态规划的理解方式有很多种，这里讲述的是yxc老师的闫氏dp法，个人认为是最好的理解方式并且非常好用。
动态规划背包,基础算法与基础数据结构,动态规划,算法,c++
遇到dp问题，首先考虑状态表示，即如何（用什么、怎么样）把一个状态表示出来，区分两个不同状态的指标数量叫维度，我们要把相同的状态放入一个集合里面去，并且规定这个集合的属性（可能是最大值、最小值、元素数量等）。在此之后，我们要考虑状态计算，即如何把当前状态的集合计算出来。在这一步，我们一般采用划分集合的方式，即将一个大的集合划分为很多小的集合，这些小的集合可以计算出来，那么大的集合也就能计算出来了。一般要求是：划分集合时不重不漏。

听起来很抽象，确实是这样。dp问题需要不断做题积累经验，才能真正体会到其中的精髓。下面用背包问题来走一遍这个流程，方便理解。

背包问题是动态规划问题里的一种很常见题型，具体来说就是，给一个容量确定的背包，给一些体积确定、价值确定的物品，问怎样带才能带走价值最大的物品。好比说打游戏时，打怪掉落了很多物资，但是背包有限，就要想想带走什么才对自己最有用。我们用闫氏dp法来走一遍流程。

首先，考虑如何表示一个背包的状态：1.背包容量；2.放哪些物品。因此，背包问题集合的维度是二维的。具体表示方法不同的题目不同。因为问题需要，所以集合的属性自然就是价值的最大值。
然后就要考虑状态的计算了，即如何计算 $f (i, j)$ 的值。这个过程我们采取划分集合的方式，不同的题目有不同的考虑方式，下面用一些例题来实战。

2、01背包

01背包具体是：一个物品只有选（1）或不选（0）两种状态，固称为01背包。首先看一下例题 acwing 01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品体积是 $v_i$ ，价值是 $w_i$ 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 $v_i$ , $w_i$ ，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0< $v_i$ , $w_i$ ≤1000
输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

我们可以用 $f (i, j)$ 来表示：只在前 $i$ 个物品里面选，且背包容量为 $j$ 。

划分集合时可以将只在前 $i$ 个物品里选划分为两个小集合：

所有选了 $i$ 的选法： $f(i-1,j-v_i)+w_i$ ；
所有不选 $i$ 的选法： $f (i - 1, j)$ 。

这样就能不重不漏的把 $f (i, j)$ 分为两个小的集合了。同时由于 $f (i, j)$ 的属性是最大值，那么就可以表示为：
$f(i,j)=max(f(i-1,j-v_i)+w_i, f(i-1,j))$
这样就得到了dp问题最重要的状态计算方程。

得到了这个，这个题就可以直接做出来了：

#include <iostream>

using namespace std;

const int N = 1010;

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

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

	//因为i等于0的时候f(i,j)一定是0（选0个物品），所以直接从1开始
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            //只有装得下物品i时，才考虑选了i的选法
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m];

    return 0;
}

dp问题就是这样神奇，看似很难，其实只要得到状态计算方程，很简洁的代码就能通过。

接下来，还能对代码进行优化。注意到 $f(i,j)=max(f(i-1,j-v_i)+w_i, f(i-1,j))$ ，每个 $i$ 状态都是由 $i - 1$ 状态得到的，因此可以用滚动数组的方式来更新。意思是：一个二维数组，每行都是由上一行得到的，那么就可以优化为一个一维数组，每次用新的值覆盖当前值，也即相当于由上一行得到下一行。那么核心部分代码：

f[i][j] = f[i - 1][j];

就可以优化为：

f[j] = f[j];

恒等式可以省略；其次第二个核心代码：

if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

可以优化为：

if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);

而由于循环是递增的，所以直接从v[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]);

但是这里有一个问题：注意到 $f [j - v [i]]$ 一定小于 $f [j]$ ，所以它一定会在 $f [j]$ 之前更新，那么更新 $f [j]$ 时，就相当于用本层的 $f [j - v [i]]$ 来更新，但计算公式要求用上一层的 $f [j - v [i]]$ 来更新，为解决这个问题，只需要把第二层循环逆向进行即可。这样能保证更新 $f [j]$ 时用到的是上一层的 $f [j - v [i]]$ 。

那么得到01背包问题的终极版代码：

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    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 = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m];

    return 0;
}

3、完全背包

完全背包就是给出一些物品，但是物品数量不限。例题 acwing完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 $v_i$ ，价值是 $w_i$ 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 $v_i$ , $w_i$ ，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0< $v_i$ , $w_i$ ≤1000
输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

还可以用 $f (i, j)$ 来表示：只在前 $i$ 个物品里面选，且背包容量为 $j$ 。
但是划分集合的时候，就和01背包略有不同了。因为物品是无限使用，所以划分为：

第 $i$ 件物品选了0个的选法： $f (i - 1, j)$ ；
第 $i$ 件物品选了1个的选法： $f(i-1,j-v_i)+w_i$ ；
第 $i$ 件物品选了2个的选法： $f(i-1,j-2v_i)+2w_i$ ；
……
第 $i$ 件物品选了s个的选法： $f(i-1,j-sv_i)+sw_i$ ，（ $s×v_i≤j$ ）；

这样就能做到不重不漏地把 $f (i, j)$ 划分为了 $s$ 个集合。所以可以得到状态计算方程：
$f(i,j)=max(f(i-1,j-kv_i)+kw_i)，(k=0,1,2,…,s)$

那么题解就有了：

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    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;

    return 0;
}

可以进行进一步优化。这里注意到一个神奇的事情：
动态规划背包,基础算法与基础数据结构,动态规划,算法,c++
也即，当 $v_i≥j$ 时，有 $f(i,j)=f(i,j-v_i)+w_i$ 。
有了这个，就可以对完全背包进行优化了：

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    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 ++ )
        {
            f[i][j] = f[i - 1][j];
            if (v[i] <= j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

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

    return 0;
}

这样少了一重循环，时间复杂度就变成O(mn)了。
再和01背包一样进行一维优化，得到最终版代码：

#include <iostream>

using namespace std;

const int N = 1010;

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

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

    for (int i = 1; i <= n; i ++ )
    	//注意这里的区别是j递增，和01背包相反，一定要想清为什么
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

$j$ 是递增的原因：公式中 $f (i, j)$ 的更新就是用本层的 $f(i,j-v_i)$ 。

4、多重背包问题

完全背包就是给出一些物品，但是物品数量有限。例题 acwing多重背包

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 $s_i$ 件，每件体积是 $v_i$ ，价值是 $w_i$ 。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 $v_i$ , $w_i$ , $s_i$ ，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0< $v_i$ , $w_i$ , $s_i$ ≤2000
输入样例

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

输出样例：

10

用 $f (i, j)$ 来表示：只在前 $i$ 个物品里面选，且背包容量为 $j$ 。
划分集合的时候，因为物品是有限使用，所以划分为：

第 $i$ 件物品选了0个的选法： $f (i - 1, j)$ ；
第 $i$ 件物品选了1个的选法： $f(i-1,j-v_i)+w_i$ ；
第 $i$ 件物品选了2个的选法： $f(i-1,j-2v_i)+2w_i$ ；
……
第 $i$ 件物品选了 $s_i$ 个的选法： $f(i-1,j-sv_i)+sw_i$ ；

这样就能做到不重不漏地把 $f (i, j)$ 划分为了 $s$ 个集合。所以可以得到状态计算方程：
$f(i,j)=max(f(i-1,j-kv_i)+kw_i)，(k=0,1,2,…)$
注意这里的 $kv_i$ 一定是小于 $j$ 的。

那么就可以得到题解：

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N];
int v[N], w[N], s[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 * v[i] <= j && k <= s[i]; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

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

    return 0;
}

但是浅看一下时间复杂度，三重循环，最坏 $1000 \times 2000 \times 2000$ ，大约是四十亿，明显超时了（C++每秒大概运算一亿次），所以就要优化。这里的优化是一个技巧，叫二进制优化。

假设有1023个物品，那么进行分组：2⁰,2¹,2²,2³,2⁴,…,2⁹。也即1,2,4,8,…,512。用这几个数，就能组合出0 ~ 1023中所有的数。那么原来的1024（0 ~ 1023）个数，就变成了10个数进行组合。假如物品数不是2ⁿ-1个，例如45，那么就分组：2⁰,2¹,2²,2³,2⁴,45-2⁴。也就是1,2,4,8,16,14。用这几个数就能组合出0 ~ 45所有的数了。

把分的每个组想成一个物品，其实就转化成了01背包问题，因为每组只能是选或不选。因此用01背包的代码即可解决，重点是分组。这时看一下时间复杂度，也就是 $V×N×logs_i$ ，差不多 $1000 \times 2000 \times l o g 2000$ ，大概两千万，可以接受。那么给出优化的多重背包问题：

#include <iostream>

using namespace std;

//物品总数大概是N(组数)*log si(每组里的小组数)
//1000*log2000≈11000
const int N = 11010, M = 2010;

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

int main()
{
    cin >> n >> m;
    
    //分组
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    
    //分组后的物品数
    n = cnt;
    
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    cout << f[m] << endl;
    
    return 0;
}

5、分组背包问题

分组背包问题简单来说就是每组只能选一个物品或不选。
例题 acwing分组背包

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$ ，价值是 $w_{ij}$ ，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 $S_i$ ，表示第 i 个物品组的物品数量；
每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij}$ , $w_{ij}$ ，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0< $S_i$ ≤100
0< $v_{ij}$ , $w_{ij}$ ≤100
输入样例

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

输出样例：

8

用 $f (i, j)$ 来表示：只在前 $i$ 组里面选，且背包容量为 $j$ 。
划分集合的时候，因为物品是有限使用，所以划分为：

第 $i$ 组物品不选的选法： $f (i - 1, j)$ ；
第 $i$ 组物品选第1个的选法： $f(i-1,j-v_{i1})+w_{i1}$ ；
第 $i$ 组物品选第2个的选法： $f(i-1,j-v_{i2})+w_{i2}$ ；
……
第 $i$ 组物品选第 $s_i$ 个的选法： $f(i-1,j-v_{is_i})+w_{is_i}$ ；

由于思路较为简单，所以直接给出一维优化后的代码：文章来源地址https://www.toymoban.com/news/detail-738959.html

#include <iostream>

using namespace std;

const int N = 110;

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

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 1; 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] << endl;
    
    return 0;
}