%%%

Texas_the_Omertosa · 2025-08-27 09:23:21 · 个人记录

背包问题总结

题单地址：https://www.luogu.com.cn/training/5197

题目摘要

1. P1048 [NOIP 2005 普及组] 采药：01 背包，最大化价值。草药是物品，时间是体积，价值是价值。

2. P1049 [NOIP 2001 普及组] 装箱问题：01 背包，最大化价值。物品是物品，体积同时是体积和价值。

3. P1164 小A点菜：01 背包，要求恰好装满的方案数。菜是物品，价格是体积。

4. P3985 不开心的金明：01 背包，最大化价值。物品是物品，价格是体积，重要度是价值。由于体积太大，无法直接表示。根据题目限制，可以用 (选取的物品个数, 与最小可能的体积之差) 表示，有效体积在 O(N \times 3N)。总复杂度为 O(3\times N^3)。

5. P1060 [NOIP 2006 普及组] 开心的金明：01 背包，最大化价值。物品是物品，价格是体积，重要度是价值。

6. P1616 疯狂的采药：完全背包，最大化价值。草药是物品，时间是体积，价值是价值。

7. P2722 [USACO3.1] 总分 Score Inflation：完全背包，最大化价值。题目是物品，时间是体积，分数是价值。

8. P1853 投资的最大效益：完全背包，最大化价值。

   按年进行 DP 的话需要知道投资组合以及剩余钱数，状态太多。

   由于投资可以和钱无损转换，因此可以年末统一卖掉所有资产，然后下一年初重新买入即可。因此只需要解决在年初如何投资使得年末可以获得最大收益即可，该问题为一个完全背包，要求最大化价值。投资额是体积，本金和年利息是价值。

   钱的范围为 10^6 太大，还需要优化。由于投资额一定是 1000 的倍数，因此钱数可以对 1000 写成带余除法的形式，只有商有用。复杂度为 O(n \times (s \times 1.1^d / 1000) \times d)。

9. P2918 [USACO08NOV] Buying Hay S：完全背包变种。干草包是物品，重量 P 是体积，开销是代价。为了满足在采购至少 H 磅干草前提下最小化代价，可以求一个 H + P_\max 体积范围内的，恰好装满，最小化代价的完全背包。然后在 [H, H + P] 取最小值即可。

10. P1833 樱花：多重背包和完全背包混合，最大化价值。樱花树是物品，时间是体积，美学值是价值。要用二进制优化。

11. P5365 [SNOI2017] 英雄联盟：分组背包变种。根据题目中描述的过程，可将每个英雄买不同数量的皮肤认为是一个物品组，体积是皮肤数量（以乘积的形式占据体积），代价是金币。然而体积的范围太大，需要优化。

    根据题目限制，购买的皮肤数目为 170 个时，必定超过要求，因此花费的金币数目不超过 170 \times 199 = 33830，是个较小的范围，因此尝试将金币数目作为体积，组成的方案数作为价值，目标是在给定体积下最大化价值。最小的，满足此时价值大于等于给定值，的体积，即为答案。

12. P2347 [NOIP 1996 提高组] 砝码称重：多重背包，要求可达的体积的数目。

13. P1776 宝物筛选：多重背包，最大化价值。需要用到二进制优化。

14. P1782 旅行商的背包：多重背包和分组背包混合，最大化价值。分为两部分，第一部分为朴素的多重背包，需要二进制优化。第二部分为分组背包。

15. P1855 榨取kkksc03：01 背包，多维背包，最大化价值。愿望是物品，(金钱, 时间) 是体积，数量是价值。

16. P1507 NASA的食物计划：01 背包，多维背包，最大化价值。食品是物品，(体积, 质量) 是体积，卡路里是价值。

17. P1541 [NOIP 2010 提高组] 乌龟棋：模拟过程，令 f[s][c_1][c_2][c_3][c_4] 表示当前在 s，已经花费步长为 i 的卡 c_i 张时的最大得分。根据最后一步使用的卡的种类分类讨论，转移方程易得。然而复杂度太大，需要优化。

    转移已是 O(1)，只有状态可以优化。注意到 f 中其实有很多状态是不合法的，需要满足 s = 1 \times c_2 + 2 \times c_2 + 3 \times c_3 + 4 \times c_4。由于 s 可以通过 c_i 计算得到，因此可以省去 s 这一维。

    复杂度 O(C^4) = O(40^4)。

18. P2732 [USACO3.3] 商店购物 Shopping Offers：完全背包，多维背包，最小化代价。优惠是物品，每种商品数量的组合是体积，价格是代价。

19. P2851 [USACO06DEC] The Fewest Coins G：

20. P1757 通天之分组背包：分组背包。复杂度为 O(m \times \sum_i k_i) = O(m \times n)。

21. P5322 [BJOI2019] 排兵布阵：分组背包。枚举每个城堡派遣的人数计算得分构建物品组。复杂度大了一些，需要优化。

    注意到每个城堡中只有在某个人派遣人数的两倍才有效，从而可以缩减物品组内数目。

    • 但实际优化后的复杂度理论上也过不了这个题。

22. P1064 [NOIP 2006 提高组] 金明的预算方案：分组背包，最大化价值。通过主件构建物品组，价格是体积，重要度之和是价值。

23. P1273 有线电视网：树上背包。复杂度 O(NM)。

24. P5662 [CSP-J2019] 纪念品：如果要模拟过程 DP，会发现需要关心：1. 拥有的钱数；2. 每种物品的购买数量。发现 2 太大，需要优化。

    为什么要记录 2，是因为可能之前某天买的物品，在很多天之后卖掉，时间跨度过长。尝试局部化。

    发现由于物品和钱在一天中是等价的，因此可以统一在一天的开始把所有物品都换成钱，然后在一天的结束把钱在换成物品带到第二天。因此天与天之间只需要做一个完全背包最大化携带物品过夜能得到的金币数即可。

25. P4141 消失之物：回退背包。

26. P1941 [NOIP 2014 提高组] 飞扬的小鸟

技巧/模型总结

01 背包

1. P1048 [NOIP 2005 普及组] 采药：01 背包，最大化价值。草药是物品，时间是体积，价值是价值。

2. P1049 [NOIP 2001 普及组] 装箱问题：01 背包，最大化价值。物品是物品，体积同时是体积和价值。

3. P1164 小A点菜：01 背包，要求恰好装满的方案数。菜是物品，价格是体积。

4. P3985 不开心的金明：01 背包，最大化价值。物品是物品，价格是体积，重要度是价值。由于体积太大，无法直接表示。根据题目限制，可以用 (选取的物品个数, 与最小可能的体积之差) 表示，有效体积在 O(N \times 3N)。总复杂度为 O(3\times N^3)。

5. P1060 [NOIP 2006 普及组] 开心的金明：01 背包，最大化价值。物品是物品，价格是体积，重要度是价值。

完全背包

1. P1616 疯狂的采药：完全背包，最大化价值。草药是物品，时间是体积，价值是价值。

2. P2722 [USACO3.1] 总分 Score Inflation：完全背包，最大化价值。题目是物品，时间是体积，分数是价值。

3. P1853 投资的最大效益：完全背包，最大化价值。

   按年进行 DP 的话需要知道投资组合以及剩余钱数，状态太多。

   由于投资可以和钱无损转换，因此可以年末统一卖掉所有资产，然后下一年初重新买入即可。因此只需要解决在年初如何投资使得年末可以获得最大收益即可，该问题为一个完全背包，要求最大化价值。投资额是体积，本金和年利息是价值。

   钱的范围为 10^6 太大，还需要优化。由于投资额一定是 1000 的倍数，因此钱数可以对 1000 写成带余除法的形式，只有商有用。复杂度为 O(n \times (s \times 1.1^d / 1000) \times d)。

4. P2918 [USACO08NOV] Buying Hay S：完全背包变种。干草包是物品，重量 P 是体积，开销是代价。为了满足在采购至少 H 磅干草前提下最小化代价，可以求一个 H + P_\max 体积范围内的，恰好装满，最小化代价的完全背包。然后在 [H, H + P] 取最小值即可。

5. P1833 樱花：多重背包和完全背包混合，最大化价值。樱花树是物品，时间是体积，美学值是价值。要用二进制优化。

6. P5662 [CSP-J2019] 纪念品：如果要模拟过程 DP，会发现需要关心：1. 拥有的钱数；2. 每种物品的购买数量。发现 2 太大，需要优化。

   为什么要记录 2，是因为可能之前某天买的物品，在很多天之后卖掉，时间跨度过长。尝试局部化。

   发现由于物品和钱在一天中是等价的，因此可以统一在一天的开始把所有物品都换成钱，然后在一天的结束把钱在换成物品带到第二天。因此天与天之间只需要做一个完全背包最大化携带物品过夜能得到的金币数即可。

7. P1941 [NOIP 2014 提高组] 飞扬的小鸟

8. P2851 [USACO06DEC] The Fewest Coins G

多重背包

1. P1833 樱花：多重背包和完全背包混合，最大化价值。樱花树是物品，时间是体积，美学值是价值。要用二进制优化。
2. P2347 [NOIP 1996 提高组] 砝码称重：多重背包，要求可达的体积的数目。
3. P1776 宝物筛选：多重背包，最大化价值。需要用到二进制优化。
4. P1782 旅行商的背包：多重背包和分组背包混合，最大化价值。分为两部分，第一部分为朴素的多重背包，需要二进制优化。第二部分为分组背包。

二进制分组

1. P1833 樱花：多重背包和完全背包混合，最大化价值。樱花树是物品，时间是体积，美学值是价值。要用二进制优化。
2. P1776 宝物筛选：多重背包，最大化价值。需要用到二进制优化。
3. P1782 旅行商的背包：多重背包和分组背包混合，最大化价值。分为两部分，第一部分为朴素的多重背包，需要二进制优化。第二部分为分组背包。

分组背包

1. P5365 [SNOI2017] 英雄联盟：分组背包变种。根据题目中描述的过程，可将每个英雄买不同数量的皮肤认为是一个物品组，体积是皮肤数量（以乘积的形式占据体积），代价是金币。然而体积的范围太大，需要优化。

   根据题目限制，购买的皮肤数目为 170 个时，必定超过要求，因此花费的金币数目不超过 170 \times 199 = 33830，是个较小的范围，因此尝试将金币数目作为体积，组成的方案数作为价值，目标是在给定体积下最大化价值。最小的，满足此时价值大于等于给定值，的体积，即为答案。

2. P1782 旅行商的背包：多重背包和分组背包混合，最大化价值。分为两部分，第一部分为朴素的多重背包，需要二进制优化。第二部分为分组背包。

3. P1757 通天之分组背包：分组背包。复杂度为 O(m \times \sum_i k_i) = O(m \times n)。

4. P5322 [BJOI2019] 排兵布阵：分组背包。枚举每个城堡派遣的人数计算得分构建物品组。复杂度大了一些，需要优化。

   注意到每个城堡中只有在某个人派遣人数的两倍才有效，从而可以缩减物品组内数目。

   • 但实际优化后的复杂度理论上也过不了这个题。

5. P1064 [NOIP 2006 提高组] 金明的预算方案：分组背包，最大化价值。通过主件构建物品组，价格是体积，重要度之和是价值。

多维背包

1. P1855 榨取kkksc03：01 背包，多维背包，最大化价值。愿望是物品，(金钱, 时间) 是体积，数量是价值。
2. P1507 NASA的食物计划：01 背包，多维背包，最大化价值。食品是物品，(体积, 质量) 是体积，卡路里是价值。
3. P2732 [USACO3.3] 商店购物 Shopping Offers：完全背包，多维背包，最小化代价。优惠是物品，每种商品数量的组合是体积，价格是代价。

树上背包

1. P1273 有线电视网：树上背包。复杂度 O(NM)。

回退背包

1. P4141 消失之物：回退背包。

其他技巧

技巧：

1. 名字
2. 含义
3. 动机
4. 方法
   1. 具体操作过程
   2. 适用条件
5. 例子

反转价值和体积

含义：通常情况下，体积在状态中，价值为最优化的值。反转价值和体积的意思即为讲价值存在状态中，最优化体积的值。

动机：价值相比体积范围太大，存不下或者计算复杂度太高，通过该技巧可以缩减计算范围。

方法：将价值放到状态中，体积放到最优化的值中。

适用条件：计算体积和价值的范围，看谁的范围小，把谁放在状态中。

例子：

1. P5365 [SNOI2017] 英雄联盟：分组背包变种。根据题目中描述的过程，可将每个英雄买不同数量的皮肤认为是一个物品组，体积是皮肤数量（以乘积的形式占据体积），代价是金币。然而体积的范围太大，需要优化。

   根据题目限制，购买的皮肤数目为 170 个时，必定超过要求，因此花费的金币数目不超过 170 \times 199 = 33830，是个较小的范围，因此尝试将金币数目作为体积，组成的方案数作为价值，目标是在给定体积下最大化价值。最小的，满足此时价值大于等于给定值，的体积，即为答案。

2. 反转价值和体积

   1. P5365 [SNOI2017] 英雄联盟：分组背包变种。根据题目中描述的过程，可将每个英雄买不同数量的皮肤认为是一个物品组，体积是皮肤数量（以乘积的形式占据体积），代价是金币。然而体积的范围太大，需要优化。

      根据题目限制，购买的皮肤数目为 170 个时，必定超过要求，因此花费的金币数目不超过 170 \times 199 = 33830，是个较小的范围，因此尝试将金币数目作为体积，组成的方案数作为价值，目标是在给定体积下最大化价值。最小的，满足此时价值大于等于给定值，的体积，即为答案。

3. 状态太多的缩减方式

   1. 能否有简化表示
      含义：将可以计算得到的或通用的部分进行简化
      动机：本身状态过多且某些状态可以通过计算或传递而间接得到
      方法：去掉不必要的状态或更改为更简单且正确的状态
      适用条件: 状态过多导致计算繁复或复杂度过高

      例子

      1. P3985 不开心的金明：01 背包，最大化价值。物品是物品，价格是体积，重要度是价值。由于体积太大，无法直接表示。根据题目限制，可以用 (选取的物品个数, 与最小可能的体积之差) 表示，有效体积在 O(N \times 3N)。总复杂度为 O(3\times N^3)。

      2. P1853 投资的最大效益：完全背包，最大化价值。

         按年进行 DP 的话需要知道投资组合以及剩余钱数，状态太多。

         由于投资可以和钱无损转换，因此可以年末统一卖掉所有资产，然后下一年初重新买入即可。因此只需要解决在年初如何投资使得年末可以获得最大收益即可，该问题为一个完全背包，要求最大化价值。投资额是体积，本金和年利息是价值。

         钱的范围为 10^6 太大，还需要优化。由于投资额一定是 1000 的倍数，因此钱数可以对 1000 写成带余除法的形式，只有商有用。复杂度为 O(n \times (s \times 1.1^d / 1000) \times d)。

      3. P1541 [NOIP 2010 提高组] 乌龟棋：模拟过程，令 f[s][c_1][c_2][c_3][c_4] 表示当前在 s，已经花费步长为 i 的卡 c_i 张时的最大得分。根据最后一步使用的卡的种类分类讨论，转移方程易得。然而复杂度太大，需要优化。

         转移已是 O(1)，只有状态可以优化。注意到 f 中其实有很多状态是不合法的，需要满足 s = 1 \times c_2 + 2 \times c_2 + 3 \times c_3 + 4 \times c_4。由于 s 可以通过 c_i 计算得到，因此可以省去 s 这一维。

         复杂度 O(C^4) = O(40^4)。

   2. 上界的精确估计

      1. P2918 [USACO08NOV] Buying Hay S：完全背包变种。干草包是物品，重量 P 是体积，开销是代价。为了满足在采购至少 H 磅干草前提下最小化代价，可以求一个 H + P_\max 体积范围内的，恰好装满，最小化代价的完全背包。然后在 [H, H + P] 取最小值即可。
      2. P2851 [USACO06DEC] The Fewest Coins G

   3. 局部化

      1. P1853 投资的最大效益：完全背包，最大化价值。

         按年进行 DP 的话需要知道投资组合以及剩余钱数，状态太多。

         由于投资可以和钱无损转换，因此可以年末统一卖掉所有资产，然后下一年初重新买入即可。因此只需要解决在年初如何投资使得年末可以获得最大收益即可，该问题为一个完全背包，要求最大化价值。投资额是体积，本金和年利息是价值。

         钱的范围为 10^6 太大，还需要优化。由于投资额一定是 1000 的倍数，因此钱数可以对 1000 写成带余除法的形式，只有商有用。复杂度为 O(n \times (s \times 1.1^d / 1000) \times d)。

      2. P5662 [CSP-J2019] 纪念品：如果要模拟过程 DP，会发现需要关心：1. 拥有的钱数；2. 每种物品的购买数量。发现 2 太大，需要优化。

         为什么要记录 2，是因为可能之前某天买的物品，在很多天之后卖掉，时间跨度过长。尝试局部化。

         发现由于物品和钱在一天中是等价的，因此可以统一在一天的开始把所有物品都换成钱，然后在一天的结束把钱在换成物品带到第二天。因此天与天之间只需要做一个完全背包最大化携带物品过夜能得到的金币数即可。

      3. P1006 [NOIP 2008 提高组] 传纸条

      4. P4870 [BalticOI 2009] 甲虫 (Day1)