← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3768.c

最优子结构保留子问题最优解

理解等级:中级

若原问题的一个整体最优解中,包含其子问题的最优解,就具有最优子结构。它说明缩小问题规模后,子问题的最优结果仍可嵌入整体解;但这项性质本身不保证贪心选择正确,还须另证局部选择能安全进入整体最优解,见 [[贪心选择须能延伸为全局最优]]。

示例(补充教学示例,非书中数据):容量 50 的分数背包若最优方案先装满密度最高的 10kg 物品,则剩余容量 40 上的装填必须仍是“容量 40 的同类背包”的最优解。若剩余 40 不是最优,换成更优装填会抬高总价值,与原方案最优矛盾。

0-1 背包也有最优子结构(决定某件装或不装后,剩余容量仍应最优),但缺少贪心选择性质,密度贪心不能保证整体最优,见 [[价值密度贪心可能输给0-1组合]]。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 122 项《12.1 从背包问题了解贪心算法》(源文件:`_epub-src/EPUB/xhtml/chapter12_0002.xhtml`) - 结论依据:原文将“问题最优解包含子问题最优解”定义为最优子结构,并称为可用贪心的关键特征;同章分数背包是先取当前最高密度再处理更小容量。容量 50→40 的演算是补充教学示例,非书中数据。 - 原始内容:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。