02.10 动态规划与贪心：有限处理预算怎样选批次
返回第二卷 · 成本模型：02.01 · 搜索不变量：02.03 · 带权路径：02.09
02.10 动态规划与贪心：有限处理预算怎样选批次
本章是面向 Go 初学者的纸上算法课：三项虚构 IM 后台任务、有限预算和人为价值只用于解释子问题、转移、表格、贪心反例与复杂度；没有运行 Go、调度器、IM 服务或基准。先会 02.01 的计数与
O记号、02.02 的数组/切片、02.03 的不变量，再读本章。当前 S2/v1正文非空且最多 6 UTF-8 B、原始 HTTP 请求正文最多 4096 B、同 ID 重复 409、非成员隐藏 404、200 accepted_in_memory只到本进程；未来 S3/v2存库提案仍为 6 B，R9 6→9 B 待审。纸上“价值最大”不修改这些合同。09.02 当前合同
一、先把任务定义成 0/1 选择，不要直接背算法名
虚构处理窗口只有 4 个预算单位，有三项不可拆、每项最多选择一次的任务：
| 任务 | 消耗的预算单位 | 纸上价值 |
|---|---|---|
A | 3 | 5 |
B | 2 | 3 |
C | 2 | 3 |
目标是在总消耗不超过 4 的情况下，让价值和最大。预算单位和价值是人为标尺，不是毫秒、货币、真实消息优先级或已批准的业务规则。若把任务拆成一半、允许重复挑 B、把价值与权限混成一个分数，就已换了问题。这是经典 0/1 背包的一个小实例：每项只有“选/不选”，不是可取小数的物品。MIT 6.006：0/1 knapsack
先不写代码，列全部合法选择：空集值 0；只取 A 值 5；只取 B/C 各值 3；B+C 消耗 2+2=4、值 6。A+B 或 A+C 消耗 5，超过预算；三项更超。因此最优是 B+C，值 6。这张小表是后面递推的金答案，也是反驳未经证明的“按比值拿最高”的依据。02.01 穷举与操作模型
二、局部选择为何会错：比值贪心的反例
常见直觉是先按“价值÷消耗”排序：A 的 5/3≈1.67，B/C 的 3/2=1.5。先拿 A 后只剩预算 1，B/C 都放不下，最终价值 5；但上一节已证明 B+C 为 6。即使 A 是单项价值最大、比值也最大，不可拆的 0/1 约束仍可能让局部优选挡住更好的组合。MIT 6.006：背包与复杂度
反例只击败这条具体贪心规则在这个问题上的最优保证，不表示所有贪心算法都错。若任务可按比例拆开且价值同比例获得，问题会改变，按比值的证明可另作；IM 消息处理动作通常不能凭算法例子切成“半条发送”。若业务还要求依赖、截止时间或公平性，本章的三项表也不完整，不能把它伪称真实调度器。02.09 问题前提
三、动态规划先命名子问题，再写边界和转移
定义 dp[i][b]：只看前 i 项任务、预算上限为 b 时可得到的最大纸上价值。i 从 0 到 3，b 从 0 到 4。边界：没有任务或预算为 0 时 dp[0][b]=0、dp[i][0]=0（本例每项消耗都正）。考虑第 i 项的消耗 cost[i]、价值 value[i]：
若 cost[i] > b：dp[i][b] = dp[i-1][b]
否则：dp[i][b] = max(dp[i-1][b], dp[i-1][b-cost[i]] + value[i])
↑不选第 i 项 ↑选第 i 项且只用前 i-1 项左分支保持前 i−1 项的最佳值；右分支先为第 i 项腾出预算，再在前 i−1 项里挑最好的余下组合，所以不会重复取同一项。这就是最优子结构：一个最优方案按“选不选最后一项”落在可复用的更小问题里。不同大问题会反复需要相同 dp[i][b]，叫重叠子问题；存表避免重复算。MIT 6.006：动态规划与背包 · 02.03 不变量
若有人把右分支误写成 dp[i][b-cost[i]]+value[i]，便可能在同一层再次使用第 i 项，那已变成另一类“可重复拿”的背包。递推式不是符号游戏，索引上的 i−1 就是每项最多一次的业务约束。
四、逐格填表并追溯 B+C
按 A、B、C 顺序填表：
| 已看任务 / 预算 b | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
无任务 i=0 | 0 | 0 | 0 | 0 | 0 |
A 后 i=1 | 0 | 0 | 0 | 5 | 5 |
A、B 后 i=2 | 0 | 0 | 3 | 5 | 5 |
A、B、C 后 i=3 | 0 | 0 | 3 | 5 | 6 |
关键格 dp[3][4]：不取 C 是 dp[2][4]=5；取 C 是 dp[2][4−2]+3=dp[2][2]+3=3+3=6，所以取 C。接着回到 dp[2][2]=3：不取 B 是 dp[1][2]=0，取 B 是 dp[1][0]+3=3，所以取 B；预算归 0。得到 B+C，与穷举一致。MIT 6.006：Knapsack recurrence
若两分支价值并列，最大价值仍确定，但挑中哪组任务需另定稳定规则，例如先按任务 ID 决定。恢复选择集需要保留二维表或足够的父决策信息；只保存最后一个数字 6，无法解释为何不是某个别的组合。纸上实现可用 [][]int，但预算/价值的单位和整数上限必须先定；课程未运行 Go。
五、一维压缩省空间，循环方向保住 0/1 语义
二维表要 O(nM) 个格，n 是任务数、M 是整数预算上限（区别于任务 B）。若只需最优值，可把上一行滚动为一维 dp[b]，对每项任务按 b=M,M−1,…,cost 从大到小更新 dp[b]=max(dp[b],dp[b-cost]+value)。倒序保证本轮读到的 dp[b-cost] 还是上一个任务集合的结果，当前任务最多用一次；空间变为 O(M)，但恢复具体任务需要额外决策或重新计算。MIT 6.006：0/1 背包
反例只处理 B（消耗 2、价值 3），预算 4：若从小到大更新，先得 dp[2]=3，到 b=4 又读本轮的 dp[2] 得 6，相当于把 B 取了两次；0/1 问题里此时预算 4 的合法最大值应只有 3。所以循环方向不是小的性能细节，而是问题约束。若是“可无限次选同一种”问题，递推和遍历方向才另行讨论。MIT 6.006：背包变式
时间 O(nM) 看起来简洁，但 M 若用二进制输入、数值极大，表格可能无法接受；这是伪多项式而非对输入字节长度的一般多项式保证。预算还可能是连续时间/费用，不能不加解释就乘成数组下标；需离散化误差、改目标或选近似策略并说明质量边界。负消耗、溢出、无效任务或依赖关系也需要在递推前处理。MIT 6.006：伪多项式分析
六、贪心何时可证明：换成不带价值权重的区间选择
贪心的关键不是“看起来快”，而是能证明局部选择不会妨碍最优解。另一个虚构任务：单个处理槽不能同时执行两个时间区间，目标是选最多个互不重叠任务，每个被选任务都只贡献 1。纸上区间用 [start,end)，结束时刻等于另一项开始时刻可兼容：A=[1,4)、B=[2,3)、C=[3,5)。按最早结束时间选，先 B 后 C，可完成 2 项；先 A 只能 1 项。MIT 6.046：Interval scheduling
为何最早结束能保证这个精确定义的问题的最多项？设某个最优方案的第一项为 X，而最早结束的可选项为 G，则 end(G)≤end(X)；把 X 换成 G，不会让原本排在 X 后、从 end(X) 起可做的任务变得不可做。于是存在同样多任务且以 G 开始的最优方案，剩余问题仍是相同形状，递归/迭代选择即可。这是交换论证，不是对所有时间/价值目标的通行证。MIT 6.046：最早结束证明
若每段任务有不同价值、允许并发多个槽、必须满足成员权限或前置依赖，最早结束规则未必最优；可能要换动态规划、图模型或问题本身。第一节 0/1 背包的 A/B/C 不可分、目标为价值和，不能偷换成这节的“选最多段”。
七、把算法结果放回 IM 业务门内
本章价值 5/3/3 是人为教学分数。真实 IM 任务还可能有延迟上限、公平性、消息顺序、同一 message_id 的重复、取消、成员授权和存储确认；这些若是硬约束，不能只放在“价值”里让算法权衡掉。当前 /v1 正文最多 6 UTF-8 B、同 ID 重复 409、非成员隐藏 404，200 accepted_in_memory 不证明 B 设备收到；算法挑了某个任务，也不自动让请求合法或完成。09.02 合同 · 11.01 业务测量
应用若真考虑批次优化，应先问：预算单位是否可加、任务是否允许拆分/重复、价值由谁批准、是否存在依赖/互斥/截止、选择后是否仍须权限与资源校验、n/B 的范围多大。若条件变动，旧 dp 表与排序结果可能失效。输出除了最大值还要有被选任务、未选原因、约束版本和业务确认点；“求得最优值 6”只是纸上选择，并非 IM 投递成功。13.01 问题定义
| 方案 | 保证的纸上结论 | 不能推出 |
|---|---|---|
| 比值贪心选 A | 快速得可行值 5 | 0/1 背包最优 |
| 本章 0/1 DP 选 B+C | 在预算 4、价值 5/3/3 下最优值 6 | 权限/顺序/送达都满足 |
| 最早结束选 B、C | 单槽、等价值、不重叠时最多 2 段 | 带权或多槽仍最优 |
八、22 道分层练习：先枚举，再填表，再审前提
1–8 核模型与反例，9–16 推演转移/压缩，17–22 判断贪心条件和业务边界。所有答案都是虚构纸上结论。
基础 1–8：预算和反例
1. A、B、C 的预算消耗各是多少？
A=3，B=2，C=2；总预算 4。
2. 三项各自的纸上价值是多少？
A=5，B=3，C=3。
3. A+B 是否合法，为什么？
不合法；消耗 3+2=5，超过预算 4。
4. B+C 的消耗与价值是多少？
消耗 4、价值 6，为本例最优。
5. 按价值/消耗先挑谁，最终多少价值？
A 的比值 5/3 最高，先挑 A 后余 1，最终值 5。
6. 比值贪心为什么不能声称本例最优？
因为可行的 B+C 值 6，大于它得到的 5。
7. 0/1 中的“1”限定了什么？
每项最多取一次，不可拆份或无限重复。
8. 纸上价值能直接当真实 IM 优先级吗？
不能；它是人为教学分数，真实规则和硬约束需另定义/批准。
推演 9–16：状态、表格与复杂度
9. `dp[i][b]` 表示什么？
前 i 项中在预算不超过 b 时可得的最大价值。
10. 无任务时 `dp[0][b]` 为多少？
0。
11. `dp[3][4]` 不选 C 与选 C 各得多少？
不选为 5；选为 dp[2][2]+3=3+3=6。
12. 为何选 C 的分支引用 `i−1` 而非同一 i？
防止本轮重复选 C，保持每项最多一次。
13. 只处理 B 时，一维正序更新到预算 4 会错算多少？
会得 6，等于 B 取两次；合法的 0/1 值应为 3。
14. 一维 0/1 DP 每项预算从哪边遍历？
从预算上限 M 向该项消耗值倒序，让读到的余预算仍是上一轮结果。
15. 二维 DP 与一维压缩各需多少格量级？
二维 O(nM)，只求值的一维 O(M)；时间仍为 O(nM)。
16. 预算上限 M 数值极大却用二进制写入，`O(nM)` 是输入长度的普通多项式吗？
不是；这是伪多项式，上界仍可能无法承受。
决策 17–22：贪心条件与业务边界
17. 区间 A=[1,4)、B=[2,3)、C=[3,5)，最早结束先选谁？
先 B，再 C；二者端点相接可兼容，共 2 项。
18. 区间贪心证明为什么能把最优第一项换成 B？
B 结束不晚于原第一项，不妨碍原后续从那个结束时刻可做的任务。
19. 给区间加不同价值后可照搬“最早结束最多项”的最优保证吗？
不能；目标已改成最大价值，需重审条件和算法。
20. DP 选 B+C 就证明两项消息已送达吗？
不能；这是纸上选择，当前 S2 200 仍只到本进程内存受理。
21. 成员授权和正文 6 B 能变成可牺牲的价值分吗？
不能；它们是硬合同，先校验，不允许用更高价值抵消越权或超限。
22. 设计下一张预算 DP 表前先问哪些前提？
预算单位、可加性、任务是否可拆/重复、价值/权限、依赖/截止、n/M 规模和错误边界。
本章完成标准与后续路径
能枚举 A/B/C 的合法组合反驳比值贪心，按 dp[i][b] 填到最优值 6 并追出 B+C，解释 0/1 一维倒序、O(nM) 的伪多项式边界，以及最早结束区间贪心只在其条件下成立，才算完成本章。下一章02.11 近似与专用结构将从关键词前缀、位图、Bloom 预筛与并查集看专用结构的收益和误判风险。第二卷路线