我读到了贪婪问题的两个属性，我正在努力理解以下两者之间的区别：-
- 最优子结构性质：最优全局解包含其所有子问题的最优解
- 贪婪选择性质：通过贪婪地选择局部最优选择，可以得到全局最优解
这两个不是等价的吗？两者看起来是一样的东西；你能给我举一个例子吗？最优子结构是满足的，而贪婪选择不是？举一个例子，当贪婪的选择是满足的，而最优子结构不是？
它们不等价：
假设我们想找到树中的最小顶点覆盖，其中每个节点都有一个代价（覆盖的代价是该覆盖中节点的所有代价的总和）。这里可以使用动态编程：f(v, taken)是覆盖以v为根的子树的最小代价，使得v在覆盖中，而f(v, not taken)是覆盖该子树而不取v的最小代价。最优子结构性质成立，因为我们可以最优地求解子问题（即为每个子树找到最优解），然后将它们组合起来找到全局最优解。然而，贪婪选择性质在这里并不成立：选择一个成本最小的顶点，直到所有边都被覆盖，并不总是产生最佳结果。
如果不可能定义什么是子问题，则贪婪选择性质可能成立，但最优子结构性质则不成立。例如，霍夫曼代码构造算法总是合并两个最小的子树（并产生最优解），因此它是一个贪婪算法，但不清楚子问题是什么，因此，谈论第一个属性根本没有多大意义。
对于未来可能不熟悉顶点覆盖或动态编程的读者来说，这些定义的措辞确实让它听起来很相似。
我认为重新表述贪婪选择的一个有用方法是，最优解将始终包含贪婪算法选择的第一个选择，尽管它不一定是所述最优解中的第一选择**-->这就是它们不同的原因，因为尽管某些东西可能是最优的，并显示出贪婪的选择属性，但你还没有证明在每一步都做出了当前最最优的解。想想Prim在加权图上的MST：你可以从任何顶点开始，但这意味着算法可以在这两个解的每一步选择不同的边，但它们总是从任何给定的顶点中选择权重最低的边，因此它们具有贪婪选择特性。但你还没有证明每一步的整个解决方案都是绝对最优的，只是选择了最贪婪的选项。
这就是它们不同的原因，尽管贪婪的选择可以导致最优子结构，但这并不能证明它具有最优子结构。证明最优子结构的常见自变量是交换自变量和保持领先自变量