背包问题

---

01 背包-采药

---

• 采药

  1、采药：输入 $T$ 和 $M$ 分别表示拥有的总时间和药材种类($T \leq 1000, M \leq 100$)，对于每种药材，输入 $t_i$ 和 $v_i$ ($t_i,v_i \leq 100$)，表示采摘该药材需要的时间和药材的价值，每种药材只可采摘一次。可能输入多组数据，直到 $T$ 和 $M$ 都为 $0$ 结束。对于每组数据，输出其规定时间内能采摘的药材价值之和的最大值
  2、对于每种药材都可以用 $0$ 或 $1$ 标记状态(是否被选择)，是一个01 背包问题。运用动态规划的思想，先确定状态：令 $dp[i][j]$ 表示到第 $i$ 个物品为止，用了 $j$ 的时间，所获得的最大价值
  3、再确定转移，对于当前的 $dp[i][j]$ ，有两种情况：如果没选择当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j]$ (没有花费时间，没有增加价值，和上一个——到第 $i-1$ 个物品的状态相同)；如果选择了当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j-t[i]] + v[i]$(当前状态等同于 $dp[i-1][j-t[i]]$ 上一个物品的价值 + 当前物品价值，其中因为当前 $dp[i][j]$ 花费的总时间为 $j$，所以上一个物品的时间应为 $j-t[i]$)。总结状态转移方程为：
  $$dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]&,没选择当前物品 \\ \\ dp[i-1][j-t[i]] + v[i]&,选择了当前物品 \\ \end{array} \right. $$
  4、最后确定初始化和边界：初始化 $dp[0][i] = 0$(到第 $0$ 个物品无论花费多少时间，价值为 $0$)；边界为 $i \leq M, j \leq T$

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  int T, M;
  int dp[110][1010]; // dp[i][j] 表示到第 i 个物品花费 j 的时间的最大价值
  int t[110], v[110];
  
  void solve()
  {
      // 初始化
      for (int i = 0; i <= T; i++)
          dp[0][i] = 0;
  
      // 输入
      for (int i = 1; i <= M; i++)
          cin >> t[i] >> v[i];
  
      // 注意转移方程中，其中一种为 dp[i][j] = dp[i-1][j-t[i]] + v[i]，令 i_ = i-1，j_ = j-t[i]
      // 则隐含 i_ < i, j_ < j，所以遍历方向一定要从小到大
      // 状态转移，dp[i][j] = dp[i-1][j] 或 dp[i-1][j-t[i]] + v[i]，取大值
      for (int i = 1; i <= M; i++)
      {
          for (int j = 0; j <= T; j++)
          {
              // 注意判断时间的合法性，不要越界
              if (j - t[i] >= 0)
                  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + v[i]);
              else
                  dp[i][j] = dp[i - 1][j];
          }
      }
  
      // 输出，到第 M 个物品花费 T 时间的最大价值
      cout << dp[M][T] << '\n';
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      while (cin >> T >> M)
      {
          if (T == 0 && M == 0)
              break;
          solve();
      }
      return 0;
  }

• 滚动数组优化

  1、回顾之前的思路中，$dp[i][j]$ 所需的值只有 $dp[i-1][j]$ 与 $dp[i-1][j-t[i]]$ ，而当更新完当前 $dp[i][j]$ 后，前一行即 $dp[i-1]$ 行就不需要了。因此，实际需要的行数只需要两行，一行表示当前行，一行表示前一行
  2、由于数组的拷贝又需要开销，所以可以换一种方法实现。只开两行的数组 $dp[0][]$ 与 $dp[1][]$，当前更新第 $0$ 行时就由第 $1$ 行的状态转移过来，反之亦然。这样交替更新，就实现了滚动数组，节省空间
  3、具体地，可以通过奇偶性或位运算实现。用 $cur = i \land 1$ 标记哪一行表示当前行，则 $cur \oplus 1$ 即为另一行(上一行)。最后输出时即输出最后一行 $cur$ 的那一行，即 $dp[M \land 1][T]$

  #include <bits/stdc++.h>
  using namespace std;
  
  int T, M;
  int dp[2][1010]; // dp[i][j] 表示到第 i 个物品花费 j 的时间的最大价值
  int t[110], v[110];
  
  void solve()
  {
      // 初始化
      for (int i = 0; i <= T; i++)
          dp[0][i] = 0;
  
      // 输入
      for (int i = 1; i <= M; i++)
          cin >> t[i] >> v[i];
  
      // 注意转移方程中，其中一种为 dp[i][j] = dp[i-1][j-t[i]] + v[i]，令 i_ = i-1，j_ = j-t[i]
      // 则隐含 i_ < i, j_ < j，所以遍历方向一定要从小到大
      // 状态转移，dp[i][j] = dp[i-1][j] 或 dp[i-1][j-t[i]] + v[i]，取大值
      for (int i = 1; i <= M; i++)
      {
          // 滚动数组优化，cur 表示当前行，cur ^ 1 表示上一行(另一行)
          int cur = i & 1;
  
          for (int j = 0; j <= T; j++)
          {
              // 注意判断时间的合法性，不要越界
              if (j - t[i] >= 0)
                  dp[cur][j] = max(dp[cur ^ 1][j], dp[cur ^ 1][j - t[i]] + v[i]);
              else
                  dp[cur][j] = dp[cur ^ 1][j];
          }
      }
  
      // 输出，到第 M 个物品(最后一行的 cur = M & 1)花费 T 时间的最大价值
      cout << dp[M & 1][T] << '\n';
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      while (cin >> T >> M)
      {
          if (T == 0 && M == 0)
              break;
          solve();
      }
      return 0;
  }

• 一维优化

  1、在滚动数组中 $dp[cur][j] = max(dp[cur \oplus 1][j], dp[cur \oplus 1][j - t[i]] + v[i])$ ，其本质可看作先将上一行复制到当前行，再进行转移比较，因此可以再将其压缩为一维(省去了复制的步骤)，$dp[j]$ 表示到目前为止，花费了 $j$ 时间的最大价值
  2、此时转移方程变为 $dp[j] = max(dp[j], dp[j - t[i]] + v[i])$ ，但转移时应使用上一行时的数据，如果自左向右遍历，左侧的数据已被更新(即 $dp[j - t[i]]$ 已经变为当前行数据)。因此要自右向左遍历，范围从最大时间开始，始终满足 $j - t[i] \geq 0$

  #include <bits/stdc++.h>
  using namespace std;
  
  int T, M;
  int dp[1010]; // dp[j] 表示到当前为止花费 j 的时间的最大价值
  int t[110], v[110];
  
  void solve()
  {
      // 初始化
      for (int i = 0; i <= T; i++)
          dp[i] = 0;
  
      // 输入
      for (int i = 1; i <= M; i++)
          cin >> t[i] >> v[i];
  
      // 状态转移，dp[j] = max(dp[j], dp[j - t[i]] + v[i])
      for (int i = 1; i <= M; i++)
          // j 自右向左遍历，注意转移范围要保证 j - t[i] >= 0
          for (int j = T; j - t[i] >= 0; j--)
              dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
  
      // 输出，到最后花费 T 时间的最大价值
      cout << dp[T] << '\n';
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      while (cin >> T >> M)
      {
          if (T == 0 && M == 0)
              break;
          solve();
      }
      return 0;
  }

---

完全背包-无穷背包

---

• 无穷背包

  1、无穷背包：给定容积为 $m$ 的背包($m \leq 10^5$)，有 $n$ 种商品($n \leq 500$)，每种商品价值为 $w_i$ ($w_i \leq 10^9$)，体积为 $v_i$ ($v_i \leq m$)。若商品数量无限且可以重复放入同一商品，输出最多可以带走多少价值的物品
  2、与上一题不同，每件物品可以重复选择，是完全背包问题。运用动态规划的思想，先确定状态：令 $dp[i][j]$ 表示到第 $i$ 个物品为止，用了 $j$ 的容积，所获得的最大价值
  3、再确定转移，对于当前的 $dp[i][j]$ ，有两种情况：如果没选择当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j]$ (没有花费容积，没有增加价值，和上一个——到第 $i-1$ 个物品的状态相同)，其相当于选择了 $0$ 个第 $i$ 个物品；如果选择了当前第 $i$ 个物品，则 $dp[i][j] = dp[i][j-v[i]] + w[i]$ (当前状态等同于 $dp[i][j-v[i]]$ 当前行当前个数$-1$ 个物品的价值 + 当前物品价值，其中因为当前 $dp[i][j]$ 花费的总容积为 $j$，所以当前数量$-1$ 个物品的容积应为 $j-v[i]$)。总结状态转移方程为：
  $$dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]&,没选择当前物品 \\ \\ dp[i][j-v[i]] + w[i]&,选择了当前物品 \\ \end{array} \right. $$
  4、最后确定初始化和边界：初始化 $dp[0][i] = 0$ (到第 $0$ 个物品无论花费多少容积，价值为 $0$)；边界为 $i \leq n, j \leq m$
  5、由于朴素算法的数组大小过大，所以栈空间不足，需要用滚动数组优化为 $2$ 行的数组

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 510;
  const int A = 1e5 + 10;
  
  int m, n;       // 容积和商品种类
  int dp[N][A];   // 到第 i 个物品花费 j 容积的最大价值
  int w[N], v[N]; // 商品价值和体积
  
  void solve()
  {
      cin >> m >> n;
  
      // 初始化
      for (int i = 0; i <= m; i++)
          dp[0][i] = 0;
  
      // 输入
      for (int i = 1; i <= n; i++)
          cin >> w[i] >> v[i];
  
      // 状态转移
      for (int i = 1; i <= n; i++)
      {
          for (int j = 0; j <= m; j++)
          {
              if (j - v[i] >= 0)
                  dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
              else
                  dp[i][j] = dp[i - 1][j];
          }
      }
  
      // 输出
      cout << dp[n][m] << '\n';
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

• 滚动数组优化

  #include <bits/stdc++.h>
  using namespace std;
  
  #define int long long
  const int N = 510;
  const int A = 1e5 + 10;
  
  int m, n;       // 容积和商品种类
  int dp[2][A];   // 到第 i 个物品花费 j 容积的最大价值
  int w[N], v[N]; // 商品价值和体积
  
  void solve()
  {
      cin >> m >> n;
  
      // 初始化
      for (int i = 0; i <= m; i++)
          dp[0][i] = 0;
  
      // 输入
      for (int i = 1; i <= n; i++)
          cin >> w[i] >> v[i];
  
      // 状态转移
      for (int i = 1; i <= n; i++)
      {
          // 滚动数组优化：当前行为 cur，上一行为 cur ^ 1
          int cur = i & 1;
  
          for (int j = 0; j <= m; j++)
          {
              if (j - v[i] >= 0)
                  dp[cur][j] = max(dp[cur ^ 1][j], dp[cur][j - v[i]] + w[i]);
              else
                  dp[cur][j] = dp[cur ^ 1][j];
          }
      }
  
      // 输出，最后一行的 cur = n & 1
      cout << dp[n & 1][m] << '\n';
  }
  
  signed main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

多重背包-多重背包

---

• 多重背包

  1、多重背包：给定容积为 $m$ 的背包，有 $n$ 种商品($m,n \leq 100$)，其中每种商品只有 $s_i$ 件，价值为 $w_i$，体积为 $v_i$($s_i,w_i,v_i \leq 100$)。若可以重复放入同一商品，输出最多可以带走多少价值的物品
  2、多重背包可以看作商品限量的完全背包。对于每种商品有 $s_i$ 件，可以将其展开为 $s_i$ 件单独的只能选 $1$ 次的商品，即如有 $3$ 件商品 $A$，可看作有 $3$ 个只能选 $1$ 次的商品 $A$，此时即将其转化为01 背包解决
  3、实际实现中，并不会将展开的商品存储下来，而是读到一件商品，跑 $s[i]$ 遍一维 01 背包。但注意，只适合数据量较小的情况

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 110;
  int dp[N]; // 一维 01 背包，到当前为止花费 j 容量的最大价值
  
  void solve()
  {
      int m, n;
      cin >> m >> n;
  
      for (int i = 1; i <= n; i++)
      {
          int s, w, v;
          cin >> s >> w >> v;
  
          // 执行 s 次 01 背包
          while (s--)
              // 一维 01 背包
              for (int j = m; j - v >= 0; j--)
                  dp[j] = max(dp[j], dp[j - v] + w);
      }
  
      // 输出到最后花费 m 容积的最大价值
      cout << dp[m];
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

• 二进制优化

  1、多重背包二周目：在上题基础上，改为了 $n_i,m_i,s_i \leq 2000$
  2、由于原思路时间复杂度 $O(n*m*s_i)$，一定超时。原先的拆分思路为将 $s_i$ 拆分为 $s_i$ 个 $1$ 相加，再来表示选择 $[0, s_i]$ 个物品的情况(如 $84$ 个商品相当于从中选 $84$ 个 $1$ 个商品相加表示)
  3、那么便可以用二进制拆分的方式优化，从二进制低位向高位拆分，剩余不够拆的放在最后，例如 $s_i = 116$ 时可拆分为 $s_i = 1 + 2 + 4 + 8 + 16 + 32 + 53$ ，这样选择 $[0, s_i]$ 个物品一定能够被这些数组合得到(如 $84 = 1 + 2 + 4 + 8 + 16 + 53$ )，也可以达到原思路相同的效果
  4、此时执行01 背包时，可看作拆分出的商品被打包在一起，如上 $s_i = 116$ 时即对 $1, 2, 4, 8, \ldots, 53$ 个商品进行选择(其 $w_i,v_i$ 也对应地 $\times 1, \times 2, \times 4, \times 8, \ldots, \times 53$)

  #include <bits/stdc++.h>
  using namespace std;
  
  #define int long long
  
  const int N = 2010;
  int dp[N]; // 一维 01 背包，到当前为止花费 j 容量的最大价值
  
  void solve()
  {
      int m, n;
      cin >> m >> n;
  
      for (int i = 1; i <= n; i++)
      {
          int s, w, v;
          cin >> s >> w >> v;
  
          vector<int> vec; // 记录 s 的拆分
          // 从二进制低位向高位拆分 s
          int x = 1;
          while (s >= x)
          {
              vec.push_back(x);
              s -= x;
              x <<= 1;
          }
          // 如果还有剩余，也加入 vec
          if (s)
              vec.push_back(s);
  
          // 从 vec 中取 k 作为系数，用于表示 [0, s] 之间的所有可能
          for (int &k : vec)
              // 一维 01 背包(注意范围，v 也要乘系数)
              for (int j = m; j - k * v >= 0; j--)
                  dp[j] = max(dp[j], dp[j - k * v] + k * w);
      }
  
      // 输出到最后花费 m 容积的最大价值
      cout << dp[m];
  }
  
  signed main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

分组背包-分组背包

---

• 分组背包

  1、分组背包：给定容积为 $m$ 的背包，有 $n$ 种商品($m,n \leq 10^3$)，对于每种商品给出重量 $w_i$，价值 $v_i$，所属组别 $k_i$ ($k \leq 100$)。同一组别中只能选出一件物品，输出最多可以带走多少价值的物品
  2、分组背包可以看作有组别限制的 01 背包 。可以令 $dp[i][j]$ 表示到第 $i$ 组为止，总重量为 $j$ 的最大价值
  3、遍历 $i, j$，对于得到的第 $i$ 组：先处理没选当前组的情况，有 $dp[i][j] = dp[i-1][j]$；如果选了当前组，则遍历 $k$ 表示该组选择的物品，有 $dp[i][j] = dp[i-1][j-w[k]] + v[k]$。总结状态转移方程为：
  $$dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]&,没选当前组 \\ \\ dp[i-1][j-w[k]] + v[k]&,选了当前组 \\ \end{array} \right. $$
  4、需要注意的是，代码应单独先处理没选的情况，且选了当前组的状态应与当前的 $dp[i][j]$ (而不是 $dp[i-1][j]$ )取大(因为是在遍历中更新当前的状态)。此外，为了方便表示数据，下面代码中用vector将 $w_i, v_i, k_i$ 在一起表示

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 1e3 + 10;
  vector<pair<int, int>> K[N]; // 下标为组别，.first 为重量，.second 为价值
  int dp[N][N];                // dp[i][j] 表示到第 i 组为止，总重量为 j 的最大价值
  
  void solve()
  {
      int m, n;
      cin >> m >> n;
      for (int i = 1; i <= n; i++)
      {
          int w, v, k;
          cin >> w >> v >> k;
          K[k].push_back({w, v});
      }
  
      // 枚举组别(由于题目没给出一共多少组，此处用 n 代替组别范围，超出部分不影响实现)
      for (int i = 1; i <= n; i++)
      {
          // 枚举重量
          for (int j = 0; j <= m; j++)
          {
              // 不选这一组
              dp[i][j] = dp[i - 1][j];
  
              // 选了这一组，枚举第 i 组中选择了 k 这一物品
              for (auto &k : K[i])
              {
                  if (j - k.first >= 0)
                      dp[i][j] = max(dp[i][j], dp[i - 1][j - k.first] + k.second);
              }
          }
      }
  
      cout << dp[n][m];
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

交换状态和值-大胃王

---

• 大胃王

  1、大胃王：给出 $n$ 道菜($n \leq 80$)、甜度耐性 $X$ 和 咸度耐性 $Y$($X,Y \leq 10^4$)，再给出每道菜的甜度 $a_i$ 和 咸度 $b_i$ ($a_i, b_i \leq 10^4$)。吃过菜的甜度咸度会累加，甜度或咸度如果超过耐性就不能再吃。吃菜的顺序可以任意调整，求最多能吃多少道菜
  2、与平常不同，如果通过一维 01 背包的思路，令 $dp[i][j]$ 表示到当前菜为止总甜度为 $i$，总咸度为 $j$ 时最多吃了多少菜，思路可行但时间复杂度为 $O(n \times X^2)$ 过大。发现 $n$ 的范围远小于 $X, Y$， 此时可以交换状态和值，使得复杂度变为 $O(n^2 \times X)$
  3、令 $dp[i][j][k]$ 表示到第 $i$ 道菜为止，选了 $j$ 道菜，总甜度为 $k$ 时的最小总咸度。则状态转移方程为：
  $$dp[i][j][k] = \left\{ \begin{array}{l} dp[i-1][j][k]&,不选当前 \\ \\ dp[i-1][j-1][k-a[i]] + b[i]&,选择当前 \\ \end{array} \right.$$
  4、选择当前时，转移的条件为：$j \gt 0$ 且 $k - a[i] \geq 0$，确保操作合法。遍历时，应先遍历选择 $i, j$，后遍历代价 $k$
  5、初始化为 $INF$ (值记录最小值)，$dp[0][0][0] = 0$。最后答案通过遍历 $j, k$，判断 $dp[n][j][k]$ 是否满足要求，并记录 $j$ 的最大值即可。注意，最大值是超限前的菜数，实际可以再吃一道菜，因此答案为 $min(j + 1, n)$

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 90, M = 1e4 + 10;
  const int INF = 0x3f3f3f3f;
  
  int n, X, Y, a[N], b[N];
  int dp[N][N][M]; // 到第 i 道菜为止，选了 j 道菜，总甜度为 k 时的最小总咸度
  
  void solve()
  {
      cin >> n >> X >> Y;
      for (int i = 1; i <= n; i++)
          cin >> a[i] >> b[i];
  
      // 初始化
      memset(dp, INF, sizeof(dp));
      dp[0][0][0] = 0;
  
      for (int i = 1; i <= n; i++)
          for (int j = 0; j <= i; j++)
              for (int k = 0; k <= X; k++)
              {
                  // 不选
                  dp[i][j][k] = min(dp[i - 1][j][k], dp[i][j][k]);
                  // 选了
                  if (j && k - a[i] >= 0)
                      dp[i][j][k] = min(dp[i - 1][j - 1][k - a[i]] + b[i], dp[i][j][k]);
              }
  
      // 统计答案
      int res = 0;
      for (int j = 0; j <= n; j++)
          for (int k = 0; k <= X; k++)
              if (dp[n][j][k] <= Y)
                  res = max(res, min(j + 1, n));
  
      cout << res;
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---