动态规划：0-1背包与完全背包问题摘编

我会带着你远行 2022-08-30 04:13 163阅读 0赞

动态规划我推荐在这里学习，[https://oi-wiki.org/dp/][https_oi-wiki.org_dp]

# 0-1背包 #

首先我们看一道题  
![在这里插入图片描述][20210718215721456.png]

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 0和1 ，这类问题便被称为「0-1 背包问题」。

已知条件有第 i i i个物品的重量 w i w\_i wi，价值 V i V\_i Vi，以及背包的总容量W

我们用二维数组存储每一种情况。设dp状态 f i , j f\_\{i,j\} fi,j为只能放前i 个物品的情况下，容量为j 的背包所能达到的最大总价值。

考虑状态转移方程。假设当前已经处理好了前i-1 个物品的所有状态，那么对于第i 个物品，当其不放入背包的时候，背包的剩余容量不变，背包中的物品总价值也不变，所以这种情况的最大价值为 f i − 1 , j f\_\{i-1,j\} fi−1,j；当其放入背包时，背包的剩余容量会减小 w i w\_i wi，背包中物品的总价值会增大 v i v\_i vi，所以这种情况最大的价值为 f i − 1 , j − w i + v i f\_\{i-1,j-w\_i\}+v\_i fi−1,j−wi\+vi

所以得出状态转移方程：

f i , j = m a x ( f i − 1 , j , f i − 1 , j − w i + v i ) f\_\{i,j\}=max(f\_\{i-1,j\}, f\_\{i - 1, j - w\_i\} + v\_i) fi,j=max(fi−1,j,fi−1,j−wi\+vi)

千万不要做题、考试使用，最好用第二种

#include <iostream>
    #include <cstring>
    using namespace std;
    const int MAXN = 210;
    int main()
    { 
        int m,  n, i, x;
        int c[MAXN], w[MAXN], f[MAXN][MAXN];
        cin >> n >> m;
        for (i = 1; i <= n; i++)
        { 
            cin >> w[i] >> c[i];
        }
        memset(f, 0, sizeof(f));
        for (i = 1; i <= n; i++)
        { 
            for (x = 1; x <= m; x++)
            { 
                if (x < w[i])
                    f[i][x] = f[i - 1][x];
                else
                    f[i][x] = max(f[i - 1][x], f[i - 1][x - w[i]] + c[i]);
            }
        }
        cout << f[n][m] << endl;
        return 0;
    }

这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优化。

由于对 有影响的只有  f i − 1 , j f\_\{i-1, j\} fi−1,j，可以去掉第一维，直接用  f i f\_i fi来表示处理到当前物品时背包容量为 i 的最大价值，得出以下方程：

f j = m a x ( f j , f j − w i + v i ) f\_j = max(f\_j, f\_\{j-w\_i\} + v\_i) fj=max(fj,fj−wi\+vi)

**务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的。**

故0-1背包算法核心代码如下：

for (int i = 1; i <= n; i++)
      for (int l = W; l >= w[i]; l--) 
      	f[l] = max(f[l], f[l - w[i]] + v[i]);

例题答案代码：

#include <iostream>
    const int maxn = 13010;
    int n, W, w[maxn], v[maxn], f[maxn];
    int main() { 
      std::cin >> n >> W;
      for (int i = 1; i <= n; i++) std::cin >> w[i] >> v[i];
      for (int i = 1; i <= n; i++)
        for (int l = W; l >= w[i]; l--)
          if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];
      std::cout << f[W];
      return 0;
    }

附题目：[http://www.kencoding.net/problem.php?id=1115][http_www.kencoding.net_problem.php_id_1115]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]

# 完全背包问题 #

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

我们可以借鉴 0-1 背包的思路，进行状态定义：设 f i , j f\_\{i,j\} fi,j为只能选前i 个物品时，容量为j 的背包可以达到的最大价值。

需要注意的是，虽然定义与0-1背包类似，但是其状态转移方程与0-1背包并不相同。

可以考虑一个朴素的做法：对于第 i 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 O(N3) 的。  
![在这里插入图片描述][20210718222020539.png_pic_center]

考虑做一个简单的优化。可以发现，对于 f i , j f\_\{i,j\} fi,j，只要通过 f i , j − w i f\_\{i,j-w\_i\} fi,j−wi转移就可以了。因此状态转移方程为：

f i , j = m a x ( f i − 1 , f i , j − w i + v i ) f\_\{i,j\} = max(f\_\{i - 1\}, f\{i, j-w\_i\}+v\_i) fi,j=max(fi−1,fi,j−wi\+vi)

理由是当我们这样转移时，  f i , j − w i f\_\{i, j-w\_i\} fi,j−wi已经由  f i , j − 2 × w i f\_\{i, j-2\\times w\_i\} fi,j−2×wi 更新过，那么 f i , j − w i f\_\{i, j-w\_i\} fi,j−wi 就是充分考虑了第 i 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。

与 0-1 背包相同，我们可以将第一维去掉来优化空间复杂度。如果理解了 0-1 背包的优化方式，就不难明白压缩后的循环是正向的（也就是上文中提到的错误优化）。

例题：[「Luogu P1616」疯狂的采药][Luogu P1616]

题意概要：有 n 种物品和一个容量为 w 的背包，每种物品有重量 wi 和价值 vi 两种属性，要求选若干个物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

完全背包AC代码：

#include <iostream>
    const int maxn = 1e4 + 5;
    const int maxW = 1e7 + 5;
    int n, W, w[maxn], v[maxn];
    long long f[maxW];
    int main() { 
      std::cin >> W >> n;
      for (int i = 1; i <= n; i++) std::cin >> w[i] >> v[i];
      for (int i = 1; i <= n; i++)
        for (int l = w[i]; l <= W; l++)
          if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];
      std::cout << f[W];
      return 0;
    }

附题目：

P1048 \[NOIP2005 普及组\] 采药  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]

P1616 疯狂的采药

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]

[https_oi-wiki.org_dp]: https://oi-wiki.org/dp/
[20210718215721456.png]: /images/20220829/61a6e08860dc4c71a8642e2b197082e0.png
[http_www.kencoding.net_problem.php_id_1115]: http://www.kencoding.net/problem.php?id=1115
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/cb5f816882934033adf84724a00ee486.png
[20210718222020539.png_pic_center]: /images/20220829/03f57fc2f4194d888517967d976af8e6.png
[Luogu P1616]: https://www.luogu.com.cn/problem/P1616
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/ec7ac02b3b5c4dcbab5f70da97ae3b44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220829/965290840a8546c19facc4efd0beaeab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220829/e32120d2d22e48538737a505846be2dd.png