0/1 背包：容量 W = 10，物品 A（重 6、价值 7）、B（重 5、价值 5）、C（重 5、价值 5）。(1) 按“价值/重量”从大到小贪心装，会得到什么解？最优解的目标值是多少？这说明什么？(2) 写出用 DP 求解的状态定义和转移方程，以及时间、空间复杂度。(3) 如果把二维 DP 压成一维数组，遍历容量时应该正序还是逆序，为什么？

面试官在考什么

是否真的自己写过 0/1 背包 DP：状态与转移写不写得出、一维压缩的正逆序理由说不得清、伪多项式复杂度是否有概念。

动态规划

回答框架 · 前两步

1. 贪心按性价比：A 是 7/6 ≈ 1.17，B、C 各 1.0，先拿 A，剩容量 4 装不下 B/C，得价值 7；最优是 B + C = 10。说明 0/1 背包不满足贪心选择性质（不能切分物品填满余量）。
2. 状态 f[i][w] = 前 i 件物品、容量上限 w 时的最大价值；转移 f[i][w] = max(f[i-1][w], f[i-1][w - w_i] + v_i)（w ≥ w_i），边界 f[0][·] = 0。

同一能力域的其他题

• 你说做过排产调度，用了遗传算法/模拟退火。请说明你的编码方式（染色体/状态表示）是什么？适应度函数里有没有加惩罚项？为什么？
• 你要实现一个最小化 0-1 整数规划的分支定界求解器。某实例根节点 LP 松弛下界 = 100，已知最优整数解 = 118。跑完 10 万个节点后 incumbent 仍是 118，open list 里还有 5 万个节点，其中最好的下界是 104。请回答：(a) 你用什么指标判断瓶颈在“下界太松”还是在“分支/节点选择策略差”？(b) 如果不改模型语义，只改界的紧度，列出两种手段并说明各自代价；(c) 当前 incumbent = 118，某子节点 LP 下界恰好等于 118 且解是分数，你是否剪枝，为什么？
• 一个 0-1 整数规划模型：200 个 0-1 变量、500 条约束，用求解器跑 1 小时，MIP gap 仍有 28%。日志显示 root LP relaxation 的目标值只比初始可行解好 5%，搜索树在第 3 层就展开出上万个节点。你会优先动哪几个地方？先动哪个、为什么？
• 你负责一个生产排程的混合整数规划求解服务：约 10 万变量，约束以背包和先后关系为主，16 核机器，当前分支定界跑 20 小时仍有 5% gap，LP 重求解占 80% 时间。业务要求 2 小时内给出可执行方案。团队提出三条路线：A 自研强分支+并行 B&B；B 增加问题特定割平面；C 改用约束规划/商用求解器或启发式先给可行解。作为技术负责人，你如何诊断瓶颈、排序路线、做 build/buy 取舍，并给出 90 天落地计划与验收指标？
• 整数规划：max z = 5x1 + 4x2，约束 2x1 + 3x2 ≤ 12，2x1 + x2 ≤ 7，x1, x2 ≥ 0 且取整。它的 LP 松弛最优解是 (x1, x2) = (2.25, 2.5)，z = 21.25。请回答：(1) 你会对哪个变量分支，两个子问题分别是什么，各自 LP 上界大概是多少；(2) 如果某个子问题的 LP 松弛最优解恰好是整数解，是不是就可以直接把它从待探索列表里删掉，为什么；(3) 搜索过程中的“当前下界”是怎么来的、什么时候更新它。
• 你用列生成求解一个集合覆盖型主问题（最小化总成本）。当前 RMP 的对偶解为 π = (3, 2, 5)（对应 3 个需求）。子问题返回一条覆盖需求 2 和 3、成本为 6 的列。请回答：(a) 这条列的 reduced cost 是多少？该不该加入 RMP？(b) 列生成收敛后 RMP 的 LP 最优值是 100，四舍五入得到的整数可行解是 115，这个 gap 你打算怎么处理？(c) 如果子问题改用启发式搜索而不是精确最短路，对 (b) 中的下界和剪枝会有什么影响？