为什么贪心算法是最优的？

Question

为什么贪心算法是最优的？

8

Codility，第14课，任务TieRopes（https://codility.com/demo/take-sample-test/tie_ropes）。简要地说，问题是将正整数列表A划分为具有至少K的总和的（连续的）子列表的最大数量。

我只想出了一个贪心解决方案，因为这是这节课的名称。它通过了所有测试，但我不知道它是否是最优解（如果它是最优解的话）。

int solution(int K, vector<int> &A) {
    int sum = 0, count = 0;
    for (int a : A)
    {
        sum += a;
        if (sum >= K)
        {
            ++count;
            sum = 0;
        }
    }
    return count;
}

有人能告诉我这个解决方案是否最优以及为什么吗？

- NPS

2

证明贪心算法最优的正常模式是：（1）假设存在一种情况，贪心算法不能产生最优结果；（2）查看其解决方案和最优解决方案分歧的第一个位置；（3）证明该位置不存在。采用反证法证明。 - Sneftel

1

在我看来，“连续性”要求已经从这个问题的解决方案中消除了所有有意义的灵活性。也就是说，解决方案是显而易见和直接的：从开头开始累积一个分区，直到达到“K”，然后开始一个新的分区。它唯一允许的灵活性是在当前分区的总和已经为“K”时继续扩展当前分区，但很明显，这只会降低解决方案的质量。 - AnT stands with Russia

@AndreyT 这是你的直觉，你可能是对的，但我认为这并不足以证明。 - NPS

@NPS: 是的，我可能在这里错了。我假设我们不允许跳过分区之间的元素。但显然我们可以这样做。那么就有另一种灵活性。我们可以牺牲（跳过）一些初始元素，并从某个较晚的元素开始累积第一个分区。在分区之间也可以这样做。这样做有可能产生更好的解决方案吗？ - AnT stands with Russia

2个回答

1

这里是导致正式证明的思路。

1. 如果A是B的后缀，则A的最大分区大小小于或等于B的最大分区大小，因为我们可以将A的第一个子列表扩展以包括新元素，而不会减少其总和。

2. 每个贪婪解法中每个子列表的所有真前缀之和都小于K。

3. 没有必要留有间隙，因为我们可以将缺失的元素添加到相邻的列表中（我认为我的问题描述已经排除了这种可能性，但我仍然要说一下）。

正式证明可以通过归纳来完成，以表明对于每个非负整数i，存在与贪婪解法在每个子列表的前i个上一致的最优解法。由此可知，当i足够大时，与贪婪算法一致的唯一解法是贪婪算法，因此贪婪算法是最优解法。

基础情况 i = 0 是微不足道的，因为任意最优解都可以。归纳步骤包括找到一个与贪心算法在前 i 个子列表上一致的最优解，然后缩小第 i+1 个子列表以匹配贪心解（根据观察2，我们确实在缩小该子列表，因为它从与贪心相同的位置开始；根据观察1，我们可以相应地扩展最优解的第 i+2 个子列表）。

- David Eisenstat

我恐怕没有理解您的第二点，无论是为什么它必须成立还是为什么它有用！其余部分是有意义的，但我认为还需要明确说明任何最优解中的第一个子列表不能比贪心解中的第一个子列表更短，以解释归纳步骤中我们只需要处理的情况是缩小最优解的第(i+1)个子列表(即为什么我们永远不需要将它们扩大)。 - j_random_hacker

@j_random_hacker 这就是我的本意，我同意之前的措辞很差。 - David Eisenstat

现在我更清楚了，谢谢。就我而言，我认为不需要第三点; OP问题中的“分区”告诉我，没有解决方案可以包含间隙，并且在贪婪构造期间不会出现间隙。(我还对dasblinkenlights的提到这一点感到困惑。)虽然我正在挑剔:在“唯一与贪婪一致的解决方案是贪婪”中写下“只有”，似乎暗示着贪婪解决方案可能是唯一的，但它并不是(也不需要); AFAICT，当i = opt_number_of_sublists时，只需要找到匹配的最优解即可。 - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jdehesa · Accepted Answer

也许我有些天真或者在这里犯了一些错误，但是我认为算法的优化并不是太难（虽然不是显而易见）。

假设你有一个最大子列表数的最佳列表分区。您可能拥有列表的所有元素，也可能没有，但由于将元素添加到有效列表会生成另一个有效列表，因此让我们假设最初未分配到任何子列表中的任何可能的“剩余”元素都是随意分配给其相邻子列表之一；因此，我们有了一个适当的最优列表分区，我们将其称为P1。

现在，让我们考虑贪婪算法会产生的分区，例如P2。对于P2中的第一个子列表，有两件事情可以发生：

1.它可能与P1中的第一个子列表相同。 2.它可以比P1中的第一个子列表更短。

在1中，您将重复从第一个子列表后的下一个元素开始的推理。如果算法产生的每个后续子列表都等于P1中的那个，则P1和P2将相等。

在2中，您也会重复推理，但现在您至少有一个“额外”的项目可用。因此，下一个子列表可以：

2.1.达到P1中的下一个子列表。 2.2.在P1中的下一个子列表之前结束。

并重复。因此，在每种情况下，您将至少拥有与P1相同数量的子列表。这意味着，P2至少与列表的任何可能分区一样好，特别是任何最优分区。

这不是一个非常正式的证明，但我认为它是有效的。请指出您认为可能存在错误的地方。