动态规划专题——背包问题

🧑‍💻 文章作者:Iareges
🔗 博客主页:https://blog.csdn.net/raelum
⚠️ 转载请注明出处

目录

  • 前言
  • 一、01背包
    • 1.1 使用滚动数组优化
  • 二、完全背包
    • 2.1 使用滚动数组优化
  • 三、多重背包
    • 3.1 使用二进制优化
  • 四、分组背包
  • 总结

前言

本文主要介绍常见的四种背包问题,思维导图如下:

一、01背包

💡 现有 N N N 件物品和一个最多能承重 M M M 的背包,第 i i i 件物品的重量是 w i w_i wi,价值是 v i v_i vi。在背包能承受的范围内,试问将哪些物品装入背包后可使总价值最大,求这个最大价值。

因为每件物品只有选与不选两种状态,所以该问题又称01背包问题。

d p [ i ] [ j ] dp[i][j] dp[i][j] 的含义是:在背包承重为 j j j 的前提下,从前 i i i 个物品中选能够得到的最大价值。不难发现 d p [ N ] [ M ] dp[N][M] dp[N][M] 就是本题的答案。

如何计算 d p [ i ] [ j ] dp[i][j] dp[i][j] 呢?我们可以将它划分为以下两部分:

  • 选第 i i i 个物品:由于第 i i i 个物品一定会被选择,那么相当于从前 i − 1 i-1 i1 个物品中选且总重量不超过 j − w [ i ] j-w[i] jw[i],对应 d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] dp[i-1][j-w[i]]+v[i] dp[i1][jw[i]]+v[i]
  • 不选第 i i i 个物品:意味着从前 i − 1 i-1 i1 个物品中选且总重量不超过 j j j,对应 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]

结合以上两点可得递推公式:

d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] ,    d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) dp[i][j] = \max(dp[i-1][j],\;dp[i-1][j-w[i]]+v[i]) dp[i][j]=max(dp[i1][j],dp[i1][jw[i]]+v[i])

由于下标不能是负数,所以上述递推公式要求 j ≥ w [ i ] j\geq w[i] jw[i]。当 j < w [ i ] j<w[i] j<w[i] 时,意味着第 i i i 个物品无法装进背包,此时 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i1][j]。综合以上可得出:

d p [ i ] [ j ] = { d p [ i − 1 ] [ j ] , j < w [ i ] max ⁡ ( d p [ i − 1 ] [ j ] ,    d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) , j ≥ w [ i ] dp[i][j]= \begin{cases} dp[i-1][j],&j<w[i] \\ \max(dp[i-1][j],\;dp[i-1][j-w[i]]+v[i]),&j\geq w[i] \end{cases} dp[i][j]={dp[i1][j],max(dp[i1][j],dp[i1][jw[i]]+v[i]),j<w[i]jw[i]

d p dp dp 数组应当如何初始化呢?当背包承重为 0 0 0 时,显然装不下任何物品,所以 d p [ i ] [ 0 ] = 0    ( 1 ≤ i ≤ N ) dp[i][0]=0\;(1\leq i\leq N) dp[i][0]=0(1iN)。若一个物品也不选(即从前 0 0 0 个物品中选),此时最大价值也是 0 0 0,所以 d p [ 0 ] [ j ] = 0    ( 0 ≤ j ≤ M ) dp[0][j]=0\;(0\leq j\leq M) dp[0][j]=0(0jM)。由此可知, d p dp dp 数组应当全0初始化,即声明为全局变量。

题目链接:AcWing 2. 01背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int w[N], v[N];
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    cout << dp[n][m] << "\n";

    return 0;
}

时间复杂度为 O ( n m ) O(nm) O(nm)

1.1 使用滚动数组优化

之前我们用到的 d p dp dp 数组是二维数组,它可以进一步优化成一维数组。

观察递推公式不难发现, d p dp dp 数组中第 i i i 行的元素仅由第 i − 1 i-1 i1 行的元素得来,即第 0 0 0 行元素的更新值放到第 1 1 1 行,第 1 1 1 行元素的更新值放到第 2 2 2 行,以此类推。与其把一行的更新值放到新的一行,不如直接就地更新,因此我们的 d p dp dp 数组只需要一行来存储,即一维数组。

去掉 d p dp dp 数组的第一维后,递推公式变成:

d p [ j ] = { d p [ j ] , j < w [ i ] max ⁡ ( d p [ j ] ,    d p [ j − w [ i ] ] + v [ i ] ) , j ≥ w [ i ] dp[j]= \begin{cases} dp[j],&j<w[i] \\ \max(dp[j],\;dp[j-w[i]]+v[i]),&j\geq w[i] \end{cases} dp[j]={dp[j],max(dp[j],dp[jw[i]]+v[i]),j<w[i]jw[i]

d p [ j ] = max ⁡ ( d p [ j ] ,    d p [ j − w [ i ] ] + v [ i ] ) , j ≥ w [ i ] dp[j]= \max(dp[j],\;dp[j-w[i]]+v[i]),\quad j\geq w[i] dp[j]=max(dp[j],dp[jw[i]]+v[i]),jw[i]

原先 j j j 是从 1 1 1 遍历至 m m m 的,现在只需从 w [ i ] w[i] w[i] 遍历至 m m m。但,这个遍历顺序真的对吗?

请看下图:

红色箭头表示,在二维数组中, d p [ i ] [ j ] dp[i][j] dp[i][j] d p [ i − 1 ] [ j − w [ i ] ] dp[i-1][j-w[i]] dp[i1][jw[i]] d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j] 得来, d p [ i ] [ j + w [ i ] ] dp[i][j+w[i]] dp[i][j+w[i]] d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j] d p [ i − 1 ] [ j + w [ i ] ] dp[i-1][j+w[i]] dp[i1][j+w[i]] 得来。用一维数组的话来讲就是,第 i i i 行的 d p [ j ] dp[j] dp[j] 由第 i − 1 i-1 i1 行的 d p [ j − w [ i ] ] dp[j-w[i]] dp[jw[i]] d p [ j ] dp[j] dp[j] 得来,第 i i i 行的 d p [ j + w [ i ] ] dp[j+w[i]] dp[j+w[i]] 由第 i − 1 i-1 i1 行的 d p [ j ] dp[j] dp[j] d p [ j + w [ i ] ] dp[j+w[i]] dp[j+w[i]] 得来。

如果 j j j 从小到大遍历,那么会先更新 d p [ j ] dp[j] dp[j] 再更新 d p [ j + w [ i ] ] dp[j+w[i]] dp[j+w[i]],这就导致在更新 d p [ j + w [ i ] ] dp[j+w[i]] dp[j+w[i]] 时使用的是第 i i i 行的 d p [ j ] dp[j] dp[j] 而非第 i − 1 i-1 i1 行的 d p [ j ] dp[j] dp[j],即当 j j j 从小到大遍历时,二维数组的递推式变成了:

d p [ i ] [ j ] = { d p [ i − 1 ] [ j ] , j < w [ i ] max ⁡ ( d p [ i − 1 ] [ j ] ,    d p [ i ] [ j − w [ i ] ] + v [ i ] ) , j ≥ w [ i ] dp[i][j]= \begin{cases} dp[i-1][j],&j<w[i] \\ \max(dp[i-1][j],\;dp[i][j-w[i]]+v[i]),&j\geq w[i] \end{cases} dp[i][j]={dp[i1][j],max(dp[i1][j],dp[i][jw[i]]+v[i]),j<w[i]jw[i]

⚠️ 请牢记该式,后续讲解完全背包时会提到它。

这显然是错误的。事实上,让 j j j 从大到小遍历就不会出现这个问题。

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int w[N], v[N];
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    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--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << dp[m] << "\n";

    return 0;
}

当然, w w w 数组和 v v v 数组也是不必要的,我们可以边输入边处理,因此可以得到01背包问题的最终版代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

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

    cout << dp[m] << "\n";

    return 0;
}

到此为止,可以总结出,当 d p dp dp 数组是二维数组时, j j j 既可以从小到大遍历也可以从大到小遍历,但当 d p dp dp 数组是一维数组时, j j j 只能从大到小遍历

二、完全背包

💡 现有 N N N 种物品和一个最多能承重 M M M 的背包,每种物品都有无限个,第 i i i 种物品的重量是 w i w_i wi,价值是 v i v_i vi。在背包能承受的范围内,试问将哪些物品装入背包后可使总价值最大,求这个最大价值。

d p [ i ] [ j ] dp[i][j] dp[i][j] 的含义是:在背包承重为 j j j 的前提下,从前 i i i 物品中选能够得到的最大价值。

如何计算 d p [ i ] [ j ] dp[i][j] dp[i][j] 呢?我们可以将它划分为以下若干部分:

  • 0 0 0 个第 i i i 种物品:相当于不选第 i i i 种物品,对应 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]
  • 1 1 1 个第 i i i 种物品:对应 d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] dp[i-1][j-w[i]]+v[i] dp[i1][jw[i]]+v[i]
  • 2 2 2 个第 i i i 种物品:对应 d p [ i − 1 ] [ j − 2 ⋅ w [ i ] ] + 2 ⋅ v [ i ] dp[i-1][j-2\cdot w[i]]+2\cdot v[i] dp[i1][j2w[i]]+2v[i]
  • ⋯ \cdots

上述过程并不会无限进行下去,因为背包承重是有限的。设第 i i i 种物品最多能选 t t t 个,于是可知 t = ⌊ j w [ i ] ⌋ t=\lfloor \frac{j}{w[i]}\rfloor t=w[i]j,从而得到递推式:

d p [ i ] [ j ] = max ⁡ 0 ≤ k ≤ t d p [ i − 1 ] [ j − k ⋅ w [ i ] ] + k ⋅ v [ i ] dp[i][j]=\max_{0\leq k\leq t} dp[i-1][j-k\cdot w[i]]+k\cdot v[i] dp[i][j]=0ktmaxdp[i1][jkw[i]]+kv[i]

题目链接:AcWing 3. 完全背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int w[N], v[N];
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    cout << dp[n][m] << "\n";

    return 0;
}

若将 t t t 的值改为 min ⁡ ( 1 ,   j / w [ i ] ) \min(1,\,j/w[i]) min(1,j/w[i]),则完全背包将退化为01背包。

上述代码的时间复杂度为 O ( m 2 ∑ i w i − 1 ) ≈ O ( m 2 n ) O(m^2\sum_iw_i^{-1})\approx O(m^2n) O(m2iwi1)O(m2n),TLE是必然的。

2.1 使用滚动数组优化

考虑 d p [ i ] [ j ] dp[i][j] dp[i][j],此时第 i i i 种物品最多能选 t 1 = ⌊ j w [ i ] ⌋ t_1=\lfloor \frac{j}{w[i]} \rfloor t1=w[i]j 个,将递推式展开:

d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] ,    d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] , d p [ i − 1 ] [ j − 2 ⋅ w [ i ] ] + 2 ⋅ v [ i ] , ⋮ d p [ i − 1 ] [ j − t 1 ⋅ w [ i ] ] + t 1 ⋅ v [ i ] ) \begin{aligned} dp[i][j] = \max(dp[i-1][j],\; &dp[i-1][j-w[i]]+v[i], \\ &dp[i-1][j-2\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-t_1\cdot w[i]]+t_1\cdot v[i]) \end{aligned} dp[i][j]=max(dp[i1][j],dp[i1][jw[i]]+v[i],dp[i1][j2w[i]]+2v[i],dp[i1][jt1w[i]]+t1v[i])

下面考虑 d p [ i ] [ j − w [ i ] ] dp[i][j-w[i]] dp[i][jw[i]],此时第 i i i 种物品最多能选 t 2 = ⌊ j − w [ i ] w [ i ] ⌋ = ⌊ j w [ i ] − 1 ⌋ = t 1 − 1 t_2=\lfloor \frac{j-w[i]}{w[i]} \rfloor=\lfloor \frac{j}{w[i]}-1\rfloor=t_1-1 t2=w[i]jw[i]=w[i]j1=t11 个,相应的递推式为

d p [ i ] [ j − w [ i ] ] = max ⁡ ( d p [ i − 1 ] [ j − w [ i ] ] ,    d p [ i − 1 ] [ j − w [ i ] − w [ i ] ] + v [ i ] , d p [ i − 1 ] [ j − w [ i ] − 2 ⋅ w [ i ] ] + 2 ⋅ v [ i ] , ⋮ d p [ i − 1 ] [ j − w [ i ] − t 2 ⋅ w [ i ] ] + t 2 ⋅ v [ i ] ) \begin{aligned} dp[i][j-w[i]] = \max(dp[i-1][j-w[i]],\; &dp[i-1][j-w[i]-w[i]]+v[i], \\ &dp[i-1][j-w[i]-2\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-w[i]-t_2\cdot w[i]]+t_2\cdot v[i]) \end{aligned} dp[i][jw[i]]=max(dp[i1][jw[i]],dp[i1][jw[i]w[i]]+v[i],dp[i1][jw[i]2w[i]]+2v[i],dp[i1][jw[i]t2w[i]]+t2v[i])

又注意到 t 1 = t 2 + 1 t_1=t_2+1 t1=t2+1,上式可化简为

d p [ i ] [ j − w [ i ] ] = max ⁡ ( d p [ i − 1 ] [ j − w [ i ] ] ,    d p [ i − 1 ] [ j − 2 ⋅ w [ i ] ] + v [ i ] , d p [ i − 1 ] [ j − 3 ⋅ w [ i ] ] + 2 ⋅ v [ i ] , ⋮ d p [ i − 1 ] [ j − t 1 ⋅ w [ i ] ] + ( t 1 − 1 ) ⋅ v [ i ] ) \begin{aligned} dp[i][j-w[i]] = \max(dp[i-1][j-w[i]],\; &dp[i-1][j-2\cdot w[i]]+v[i], \\ &dp[i-1][j-3\cdot w[i]]+2\cdot v[i], \\ &\vdots \\ &dp[i-1][j-t_1\cdot w[i]]+(t_1-1)\cdot v[i]) \end{aligned} dp[i][jw[i]]=max(dp[i1][jw[i]],dp[i1][j2w[i]]+v[i],dp[i1][j3w[i]]+2v[i],dp[i1][jt1w[i]]+(t11)v[i])

将该式与 d p [ i ] [ j ] dp[i][j] dp[i][j] 的递推式比较不难发现

d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] ,    d p [ i ] [ j − w [ i ] ] + v [ i ] ) dp[i][j]=\max(dp[i-1][j],\;dp[i][j-w[i]]+v[i]) dp[i][j]=max(dp[i1][j],dp[i][jw[i]]+v[i])

根据1.1节中的结论,该式对应的是 j j j 从小到大遍历,于是我们只需把01背包问题的代码中的 j j j 改为从小到大遍历即可

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int w, v;
        cin >> w >> v;
        for (int j = w; j <= m; j++)  // 只需修改这一行
            dp[j] = max(dp[j], dp[j - w] + v);
    }

    cout << dp[m] << "\n";

    return 0;
}

优化后的时间复杂度为 O ( n m ) O(nm) O(nm)

三、多重背包

💡 现有 N N N 种物品和一个最多能承重 M M M 的背包,第 i i i 种物品的数量是 s i s_i si,重量是 w i w_i wi,价值是 v i v_i vi。在背包能承受的范围内,试问将哪些物品装入背包后可使总价值最大,求这个最大价值。

回顾完全背包问题的暴力解法,在背包承重为 j j j 的前提下,第 i i i 种物品最多能放 t = j / w [ i ] t=j/w[i] t=j/w[i] 个(这里是整除)。而在01背包问题中,第 i i i 种物品只有一个,所以应当取 t = min ⁡ ( 1 ,   j / w [ i ] ) t=\min(1,\,j/w[i]) t=min(1,j/w[i])。由此可见,对于多重背包问题,只需取 t = min ⁡ ( s [ i ] ,   j / w [ i ] ) t=\min(s[i],\,j/w[i]) t=min(s[i],j/w[i])

对完全背包问题的暴力解法做一点简单修改即可求解多重背包问题。

题目链接:AcWing 4. 多重背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int w, v, s;
        cin >> w >> v >> s;
        for (int j = 1; j <= m; j++) {
            int t = min(s, j / w);  // 只有这里需要修改
            for (int k = 0; k <= t; k++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w] + k * v);
        }
    }

    cout << dp[n][m] << "\n";

    return 0;
}

时间复杂度为 O ( m ∑ i s i ) O(m\sum_i s_i) O(misi),但还可以进一步优化。

3.1 使用二进制优化

从时间复杂度的表达式可以看出, O ( m ) O(m) O(m) 的部分已经无法再优化了,我们只能从 O ( ∑ i s i ) O(\sum_i s_i) O(isi) 入手。

先来看一个例子。水果店里有 40 40 40 个苹果,小明计划购买 n   ( 1 ≤ n ≤ 40 ) n\,(1\leq n\leq 40) n(1n40) 个苹果,试问如何让小明尽可能快速地完成购买?一个显而易见的暴力做法是,让小明一个个拿(单位是个),但效率过于低下。事实上,店员可事先准备好 6 6 6 个箱子,每个箱子中的苹果数量分别为 [ 1 , 2 , 4 , 8 , 16 , 9 ] [1,2,4,8,16,9] [1,2,4,8,16,9],再让小明按箱子拿(单位是箱子),无论小明计划购买多少个,他最多只需要拿 6 6 6 次,而在暴力做法中,小明最多需要拿 40 40 40 次。

下面用数学语言来描述上面的例子。对于任意的正整数 s s s,我们都可以找到 ⌊ log ⁡ 2 s ⌋ + 1 ≜ k \lfloor \log_2 s\rfloor+1\triangleq k log2s+1k 个正整数 a 1 , ⋯   , a k a_1,\cdots,a_k a1,,ak,使得 ∀   n ∈ [ 0 , s ] \forall\, n\in[0,s] n[0,s],都有

n = v T a , a = ( a 1 , ⋯   , a k ) T , a i = { 2 i − 1 , 1 ≤ i ≤ k − 1 s − 2 k − 1 + 1   ( ∈ [ 1 ,   2 k − 1 ] ) , i = k n=v^\mathrm{T}a,\quad a=(a_1,\cdots,a_k)^\mathrm{T},\quad a_i= \begin{cases} 2^{i-1},&1\leq i\leq k -1\\ s-2^{k-1}+1\,(\in [1,\,2^{k-1}]),&i=k\\ \end{cases} n=vTa,a=(a1,,ak)T,ai={2i1,s2k1+1([1,2k1]),1ik1i=k

其中 v = ( v 1 , ⋯   , v k ) T v=(v_1,\cdots,v_k)^\mathrm{T} v=(v1,,vk)T,且其分量非 0 0 0 1 1 1

感兴趣的读者可自行证明,这里不再赘述。回到本题,先不考虑背包的承重,我们在暴力求解多重背包的时候,对于每种物品 i i i,都要从 0 0 0 逐个枚举至 s [ i ] s[i] s[i],效率无疑是低下的。现在,对于每种物品 i i i,我们将这 s [ i ] s[i] s[i] 个物品分散至 ⌊ log ⁡ 2 s [ i ] ⌋ + 1 \lfloor \log_2 s[i]\rfloor+1 log2s[i]⌋+1 个「箱子」中,于是多重背包便化成了01背包。

题目链接:AcWing 5. 多重背包问题 II

多重背包问题中的一个「箱子」相当于01背包问题中的一件「物品」,因此我们需要估计出多重背包问题中到底有多少个箱子。显然箱子总数为

N = ∑ i = 1 n ( ⌊ log ⁡ 2 s [ i ] ⌋ + 1 ) ≤ ∑ i = 1 n ⌊ log ⁡ 2 2000 ⌋ + n = 11 n ≤ 11000 N=\sum_{i=1}^n(\lfloor \log_2 s[i]\rfloor+1)\leq \sum_{i=1}^n \lfloor \log_2 2000\rfloor+n=11n\leq 11000 N=i=1n(⌊log2s[i]⌋+1)i=1nlog22000+n=11n11000

#include <bits/stdc++.h>

using namespace std;

const int N = 11010, M = 2010;

int w[N], v[N];
int dp[M];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int cnt = 0;
    while (n--) {
        int a, b, s;  // a是重量, b是价值, c是数量
        cin >> a >> b >> s;
        for (int k = 1; k <= s; k *= 2) {
            cnt++;
            w[cnt] = a * k, v[cnt] = b * k;
            s -= k;
        }
        if (s > 0) {
            cnt++;
            w[cnt] = a * s, v[cnt] = b * s;
        }
    }

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

    cout << dp[m] << "\n";

    return 0;
}

优化后的时间复杂度为 O ( m ∑ i log ⁡ s i ) O(m\sum_i \log s_i) O(milogsi)

四、分组背包

💡 现有 N N N 组物品和一个最多能承重 M M M 的背包,每组物品有若干个,同一组内的物品最多只能选一个。每件物品的重量是 w i j w_{ij} wij,价值是 v i j v_{ij} vij,其中 i i i 是组号, j j j 是组内编号。在背包能承受的范围内,试问将哪些物品装入背包后可使总价值最大,求这个最大价值。

d p [ i ] [ j ] dp[i][j] dp[i][j] 的含义是:在背包承重为 j j j 的前提下,从前 i i i 物品中选能够得到的最大价值。

如何计算 d p [ i ] [ j ] dp[i][j] dp[i][j] 呢?我们可以将它划分为以下若干部分:

  • 不选第 i i i 组的物品:对应 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]
  • 选第 i i i 组的第 1 1 1 个物品:对应 d p [ i − 1 ] [ j − w [ i ] [ 1 ] ] + v [ i ] [ 1 ] dp[i-1][j-w[i][1]]+v[i][1] dp[i1][jw[i][1]]+v[i][1]
  • 选第 i i i 组的第 2 2 2 个物品:对应 d p [ i − 1 ] [ j − w [ i ] [ 2 ] ] + v [ i ] [ 2 ] dp[i-1][j-w[i][2]]+v[i][2] dp[i1][jw[i][2]]+v[i][2]
  • ⋯ \cdots
  • 选第 i i i 组的第 s [ i ] s[i] s[i] 个物品:对应 d p [ i − 1 ] [ j − w [ i ] [ s [ i ] ] ] + v [ i ] [ s [ i ] ] dp[i-1][j-w[i][s[i]]]+v[i][s[i]] dp[i1][jw[i][s[i]]]+v[i][s[i]]

直接将 d p dp dp 数组优化到一维可得递推式:

d p [ j ] = max ⁡ ( d p [ j ] ,    max ⁡ 1 ≤ k ≤ s [ i ] d p [ j − w [ i ] [ k ] ] + v [ i ] [ k ] ) dp[j]=\max(dp[j],\;\max_{1\leq k\le s[i]} dp[j-w[i][k]]+v[i][k]) dp[j]=max(dp[j],1ks[i]maxdp[jw[i][k]]+v[i][k])

题目链接:AcWing 9. 分组背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int w[N][N], v[N][N], s[N];
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
            for (int k = 1; k <= s[i]; k++)
                if (j >= w[i][k])
                    dp[j] = max(dp[j], dp[j - w[i][k]] + v[i][k]);

    cout << dp[m] << "\n";

    return 0;
}

总结

我们可以用一个公式来表示01背包、完全背包和多重背包:

d p [ i ] [ j ] = max ⁡ 0 ≤ k ≤ t d p [ i − 1 ] [ j − k ⋅ w [ i ] ] + k ⋅ v [ i ] , t = { min ⁡ ( 1 ,    j / w [ i ] ) , 01 背包 min ⁡ ( + ∞ ,    j / w [ i ] ) = j / w [ i ] , 完全背包 min ⁡ ( s [ i ] ,    j / w [ i ] ) , 多重背包 dp[i][j]=\max_{0\leq k\leq t} dp[i-1][j-k\cdot w[i]]+k\cdot v[i],\quad t=\begin{cases} \min(1,\;j/w[i]),&01背包\\ \min(+\infty,\;j/w[i])=j/w[i],&完全背包 \\ \min(s[i],\;j/w[i]),&多重背包 \end{cases} dp[i][j]=0ktmaxdp[i1][jkw[i]]+kv[i],t= min(1,j/w[i]),min(+,j/w[i])=j/w[i],min(s[i],j/w[i]),01背包完全背包多重背包

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/150109.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

抽象 I/O设备模型

I/O设备模型框架 RT-Thread提供了一套简单的I/O设备模型框架。 如图所示&#xff0c;它位于硬件和应用程序之间&#xff0c;共分成三层&#xff0c;从上到下分别是I/O设备管理层、设备驱动框架层、设备驱动层。 应用程序通过I/O设备管理接口获得正确的设备驱动&#xff0c;然…

一题带你写出图论算法模板!!!

这题是道基础的图论算法题目 注释很重要&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 在做这道题之前&#xff0c;我们先了解一下基础的图论算法吧&#xff01;&#xff01;&#xff01; 1.floyd&#xff1a; 这样可以求出所有点…

闲聊从零开发一个2D数字人流程实战

.2D数字人技术 百度&#xff0c;腾讯&#xff0c;等大厂都有自己的数字平台制作&#xff08;套壳&#xff1a;api后台转发vue前端&#xff09;&#xff0c;国外也有出名的heygen&#xff08;非常厉害一个&#xff09;通过开源项目组合实现&#xff0c;再打通每个项目已api的形…

LCD1602命令代码整合

本文为博主 日月同辉&#xff0c;与我共生&#xff0c;csdn原创首发。希望看完后能对你有所帮助&#xff0c;不足之处请指正&#xff01;一起交流学习&#xff0c;共同进步&#xff01; > 发布人&#xff1a;日月同辉,与我共生_单片机-CSDN博客 > 欢迎你为独创博主日月同…

C语言查看main函数的参数

这里写自定义目录标题 argc 代表参数的个数argv 代表参数的具体值&#xff0c;其中argv[0]代表的是可执行文件的名字&#xff0c;参考上图

微信这4个功能容易暴露隐私,记得关闭

每天高频使用微信的我们&#xff0c;常常觉得安全无忧&#xff0c;然而这样的想法并不准确。尽管微信本身的安全性能极高&#xff0c;但若我们不主动设置相关功能&#xff0c;个人隐私和位置信息仍可能被暴露。 在微信朋友圈上&#xff0c;有些人喜欢分享生活的点滴&#xff0c…

爆款标题怎么出来的?媒介盒子揭秘产出技巧

用户点开一篇文案的主要因素取决于标题是否具有吸引力&#xff0c;直观判断可能只需要半秒钟&#xff0c;用户的操作也决定了文章的点击率与阅读完成率。 然而有许多人为了取标题想破脑袋也想不出来&#xff0c;甚至文案内容出来了标题还没出来&#xff0c;今天媒介盒子就来为…

Java GUI小程序之图片浏览器

以下是一个简单的图片浏览器示例代码&#xff0c;它包含了图片放大缩小、拖拽、上一张/下一张查看等功能。你可以根据它进行扩展&#xff0c;提高用户体验。 import java.awt.BorderLayout; import java.awt.Dimension; import java.awt.event.ActionEvent; import java.awt.e…

土木非科班转码测开,斩获10家大厂offer

大家好&#xff0c;我是洋子 24届秋招基本已经落下了帷幕&#xff0c;各大互联网大厂基本也开奖完毕&#xff0c;还没有拿到满意offer的同学也不要灰心&#xff0c;积极备战明年的春招。另外&#xff0c;25届想要找暑期实习的同学也可以开始准备起来了&#xff0c;基本大厂在春…

UI自动化测试(弹出框,多窗口)

一、弹出框实战 1、在UI自动化测试中经常会遇到Alert弹出框的场景。Alert类是对话框的处理&#xff0c;主要是对alert警告框。confirm确认框&#xff0c;promp消息对话框。 text():获取alert的文本 dismiss ():点击取消 accept():接受 send-keys():输入 from selenium import …

split loop

// refactoringmotherfucker.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 //#include <iostream> #include <vector> #include <memory>// before refactoring of split loop class People { public:People(double _age,double _…

<C++> 优先级队列

目录 前言 一、priority_queue的使用 1. 成员函数 2. 例题 二、仿函数 三、模拟实现 1. 迭代器区间构造函数 && AdjustDown 2. pop 3. push && AdjustUp 4. top 5. size 6. empty 四、完整实现 总结 前言 优先级队列以及前面的双端队列基本上已经脱离了队列定…

单pipeline部署一套代码,多项目

单pipeline部署一套代码&#xff0c;多项目 pipeline {agent anyparameters {gitParameter(name: BRANCH_TAG, type: PT_BRANCH_TAG, branchFilter: origin/(.*), defaultValue: main, selectedValue: DEFAULT, sortMode: DESCENDING_SMART, description: 请选择需要部署的代码…

【Regulatory Genomics】Part2 BPNet、DeepLIFT

文章目录 Deep learning at base-resolution reveals cis-regulatory motif syntaxproblemBPNet: predicting base-resolution profiles from DNA sequenceInterpreting the predictions of BPNet1 DeepLIFT2 TF-MoDISCO3 motif syntax derived TF cooperativity Experimental …

人工智能基础_机器学习036_多项式回归升维实战3_使用线性回归模型_对天猫双十一销量数据进行预测_拟合---人工智能工作笔记0076

首先我们拿到双十一从2009年到2018年的数据 可以看到上面是代码,我们自己去写一下 首先导包,和准备数据 from sklearn.linear_model import SGDRegressor import numpy as np import matplotlib.pyplot as plt X=np.arange(2009.2020)#左闭右开,2009到2019 获取从2009到202…

Python如何使用Pyecharts+TextRank生成词云图?

Python如何使用PyechartsTextRank生成词云图&#xff1f; 1 应用场景2 关于Pyecharts2.1 Pyecharts简介2.2 Pyecharts安装2.3 Pyecharts支持的图形2.4 Pyecharts的一个示例 3 关于TextRank3.1 TextRank简介3.2 TextRank安装 4 词云图的生成过程4.1 导入需要的包4.2 目标文件4.3…

使用c++程序,实现图像平移变换,图像缩放、图像裁剪、图像对角线镜像以及图像的旋转

数字图像处理–实验三A图像的基本变换 实验内容 A实验&#xff1a; &#xff08;1&#xff09;使用VC设计程序&#xff1a;实现图像平移变换&#xff0c;图像缩放、图像裁剪、图像对角线镜像。 &#xff08;2&#xff09;使用VC设计程序&#xff1a;对一幅高度与宽度均相等的…

计算机网络五层协议的体系结构

计算机网络中两个端系统之间的通信太复杂&#xff0c;因此把需要问题分而治之&#xff0c;通过把一次通信过程中涉及的所有问题分层归类来进行研究和处理 体系结构是抽象的&#xff0c;实现是真正在运行的软件和硬件 1.实体、协议、服务和服务访问点 协议必须把所有不利条件和…

Java GUI实现五子棋游戏

五子棋是一种双人对弈的棋类游戏&#xff0c;通常在棋盘上进行。棋盘为 1515 的方格&#xff0c;黑白双方各执棋子&#xff0c;轮流在棋盘的格点上落子&#xff0c;先在横、竖、斜线上形成五个相连的同色棋子者获胜。五子棋规则简单&#xff0c;易学难精&#xff0c;兼具攻防和…

java,springboot钉钉开发连接器,自定义连接器配合流程使用,流程加入连接器,连接器发送参数,然后你本地处理修改值,返回给流程

1.绘制连接器&#xff0c;注意出餐入参的格式&#xff0c; 2.绘制流程&#xff0c;绑定连接器&#xff0c;是提交后出发还是表单值变化后 3.编写本地接口&#xff08;内网穿透&#xff09;&#xff0c;绑定连接器 钉钉开发连接器&#xff0c;自定义连接器配合流程使用&#x…