动态规划——背包问题

背包问题

背包问题是各种dp的经验总结，很多题目或多或少都有参考背包问题的思路。

背包问题大意是给定一些物品，每个物品都有限制选择的因素（比如体积）和价值，在不违反限制条件（比如背包容量）的情况下，选择物品使总价值最大。

背包问题有很多种变体，主要包括：

  1. 01背包问题：每种物品只能选或不选（选0次或1次）。
  2. 完全背包问题：每种物品可以选择无限次。
  3. 多重背包问题：每种物品有数量限制。
  4. 分组背包问题：物品被分为若干组，每组只能选一个物品。
  5. 混合背包：以上四种背包问题混在一起。
  6. 多维费用的背包问题：限定条件不止有体积，还会有其他因素（比如重量）。

除了经典的总价值最大问题，还会有：

  1. 方案总数。

  2. 最优方案。

  3. 方案可行性。

  4. 输出具体方案。

因此，背包问题种类非常繁多，题型非常丰富。但是，尽管背包有很多变形，都是从01背包问题演化过来的。

因为原文字数太多，拆分成几篇。链接：
动态规划——01背包问题-CSDN博客

动态规划——完全背包问题-CSDN博客

动态规划——多重背包问题-CSDN博客

动态规划——分组背包问题-CSDN博客

动态规划——二维、多维费用的背包问题-CSDN博客

动态规划——混合背包问题-CSDN博客

还有一个有依赖的背包问题，这个问题严格来说属于树形dp。等本人到达了那个境界再讨论。

相关OJ

01背包

  1. 01背包模板题

1267：【例9.11】01背包问题

2. 01背包问题 - AcWing题库

[P1048 NOIP 2005 普及组] 采药 - 洛谷

1290：采药

1932：【05NOIP普及组】采药

【模板】01背包

1294：Charm Bracelet

  1. 求方案数

P1164 小A点菜 - 洛谷

1291：数字组合

1295：装箱问题

11. 背包问题求方案数 - AcWing题库

  1. 求具体方案

12. 背包问题求具体方案 - AcWing题库

  1. 01背包变种（或和其他知识点一起考）

[P2946 USACO09MAR] Cow Frisbee Team S - 洛谷

1299：糖果

完全背包

  1. 模板题

1268：【例9.12】完全背包问题

3. 完全背包问题 - AcWing题库

P1616 疯狂的采药 - 洛谷

【模板】完全背包

  1. 求完全背包的方案数

1273：【例9.17】货币系统

1293：买书

  1. 完全背包的变种

[P2918 USACO08NOV] Buying Hay S - 洛谷

[P5662 CSP-J2019] 纪念品 - 洛谷

多重背包

  1. 模板题

4. 多重背包问题 I - AcWing题库

1269：【例9.13】庆功会

多重背包

  1. 二进制优化

5. 多重背包问题 II - AcWing题库

  1. 多重背包求方案数

[P1077 NOIP 2012 普及组] 摆花 - 洛谷

1959：【12NOIP普及组】摆花

分组背包OJ汇总

  1. 模板题

P1757 通天之分组背包 - 洛谷

1272：【例9.16】分组背包

  1. 分组背包变种

[P5322 BJOI2019] 排兵布阵 - 洛谷

多维费用背包OJ汇总

  1. 二维01背包模板题

8. 二维费用的背包问题 - AcWing题库

P1910 L 国的战斗之间谍 - 洛谷

  1. 二维01背包的变种

1292：宠物小精灵之收服

1271：【例9.15】潜水员

混合背包问题

1270：【例9.14】混合背包

P1833 樱花 - 洛谷

有依赖的背包问题

1844：【06NOIP提高组】金明的预算方案

# 动态规划 # 算法 # c++
Logo
天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

avatar 天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

avatar 天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

avatar 天工造物局