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

Question

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;
}

有人可以告诉我这个解决方案是否以及为何最佳？

Answer 1

也许我很天真或者在这里犯了一些错误，但我认为这并不太难（尽管不明显）看出该算法确实是最优的。

假设您有一个具有最大数量子列表的列表的最佳分区。您可能拥有也可能没有列表的所有元素，但由于将元素添加到有效列表会产生同样有效的列表，因此我们假设最初未分配给任何子列表的任何可能的“剩余”元素被任意分配给其相邻子列表之一；所以我们有一个适当的列表的最佳分区，我们将其称为 P1。

现在让我们考虑一下贪心算法将产生的分区，比如 P2。P2 中的第一个子列表可能会发生两种情况：

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

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

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

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

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

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