题目重点：N 笔 (id,size,fee) 交易装入容量 100 区块，最大化总手续费；解释最优 DP 与 fee/size 贪心反例。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每笔交易最多选一次，size 是 1..100 正整数，fee 非负，区块容量≤100，目标严格最大总 fee；若 size>100 直接不可选。
- 无 parent/child 依赖的基础版；生产 fee/size 启发式与后续依赖版单列，不误称其保证最优。
- 若输出交易 IDs 而非仅最大 fee，需记录决策或用二维 DP 回溯；题目只明说最大手续费。
解题路线
- 定义 dp[c] 为处理到当前交易时容量上限 c 可得最大 fee，初始 0。对每笔 (size,fee)，c 从 100 递减到 size，更新 dp[c]=max(dp[c],dp[c−size]+fee)。倒序保证本笔最多使用一次。
- 可保存 parent/choice 的二维状态或每步决策表回溯实际交易；若只存一维 dp 后随意回溯，可能将同一笔重复选入。
- 贪心按 fee/size 比排序并非 0-1 背包最优：容量 100，A=(60,120)、B=(50,90)、C=(50,90)，A 比率 2 高于 B/C 的 1.8，但选 A 后无法再放 B/C，fee=120；选 B+C 得 180。
- 生产若 N 极大且决策时间有硬限制，可以明确选近似/启发式并测 gap；容量固定 100 时 O(100N) 的 DP 往往仍很实用，需基于 N 与延迟数据比较。
- 若加入 parent 依赖，选子必须先选父的可能性需向面试官确认；这变成先决依赖背包，普通独立 dp 不正确。树形依赖可做树 DP 或枚举闭包，但题目不足以给唯一题解。
手动走一遍
容量 100 的三笔交易 A=(size60,fee120)、B/C=(50,90)。dp 处理 A 后 dp[100]=120；加入 B、C 后可从 dp[50]=90 与另一笔 50 组合，使 dp[100]=180。若容量循环写反成升序，单笔 B 可能被重复放两次。
规模与取舍
容量 C=100、N 笔基础题 O(NC)=O(100N) 时间、O(C) 空间；要可靠回溯可用 O(NC) 决策表。生产启发式排序 O(N log N) 但无最优保证。
易错点与追问
容易失分的边界
- 按 fee 最大或 fee/size 最大贪心就宣称最优。
- 容量循环升序，把每笔交易重复使用。
- 把 parent/child 版当无依赖背包。
- 为固定容量 100 直接上指数 DFS，忽略伪多项式 DP。
- 回溯时未保留决策，输出违反容量或重复交易。
继续深挖
- fee/size 启发式如何估计与最优的 gap？
- 有 parent 依赖时如何重定义状态？
- 若区块容量变成 10^9、size 大且 N 小如何选算法？
- 怎样在生产延迟预算下保留可解释性？
