贪心算法的正确性

Question

In non-decreasing sequence of (positive) integers two elements can be removed when . How many pairs can be removed at most from this sequence?

所以我想到了以下解决方案：

• 我把给定的序列分成两部分（第一和第二）。
• 分别为它们分配迭代器 - it_first := 0 和 it_second := 0。计数 := 0
• 当 it_second != second.length
  • 如果 2 * 第一 [it_first] <= 第二 [it_second]
    • 计数++，it_first++，it_second++
  • 其他
    • it_second++
• 计数就是答案

示例：

计数 := 0

[1,5,8,10,12,13,15,24] --> 第一个 := [1,5,8,10], 秒 := [12,13,15,24]

1. 2 * 1 ?< 12 --> 正确，count++，it_first++ 和 it_second++

2. 2 * 5 ?< 13 --> 正确，count++，it_first++ 和 it_second++

3. 2 * 8 ?< 15 --> 错误，it_second++

4. 8 ?<24 --> true, count ++it_second 到达最后一个元素 - END.

5. 计数== 3

线性复杂度（最坏的情况是没有要删除的元素。n/2个元素与n/2个元素比较）。 所以我缺少的部分是 'correctness' 算法——我读过关于贪婪算法的证明——但主要是树，我找不到类比。任何帮助，将不胜感激。谢谢！

编辑： 我所说的正确性是指： * 有用 * 它不能更快​​地完成（logn 或常量）

我想放一些图片，但由于声誉点 < 10 - 我不能。 （一开始我的意思是一个乳胶 ;)）

Answer 1

1. 正确性：

   • 假设最多可以删除的对数是k。声明：有一个最佳解决方案，其中所有对的第一个元素是数组的 k 最小元素。 证明：我将证明可以将任何解决方案转换为包含前 k 个元素作为所有对的第一个元素的解决方案。

     1. 假设我们有两对 (a, b)、(c, d)，因此 a <= b <= c <= d、2 * a <= b 和 2 * c <= d。在这种情况下，对 (a, c) 和 (b, d) 也是有效的。现在我们有 a <= c <= b <= d。因此，我们总是可以以任何对中的第一个元素不大于任何对中的第二个元素的方式转换对。

     2. 当我们有这个属性时，我们可以简单地用数组中最小的元素替换所有对的所有first所有元素中的最小元素，所有first元素中的第二小元素- 使用数组中第二小的元素，依此类推而不会使任何对无效。

   • 现在我们知道存在包含 k 个最小元素的最优解。很明显，我们不能通过采用适合每个元素的最小未使用元素（使其变大只能减少下一个元素的答案）来使答案更糟。因此，这个解是正确的。

   • 关于数组长度为奇数的情况的注意事项：中间元素的位置无关紧要：第一半或第二半。前半段没用（后半段元素不够）。如果我们把它放到后半部分，它是无用的二（假设我们拿了它。这意味着后半部分某处有"free space"。因此，我们可以将一些元素移动一个并去掉它）。

2. 时间复杂度方面的最优性：该解决方案的时间复杂度为O(n)。在最坏的情况下，我们无法在不阅读整个输入的情况下找到答案，而阅读已经是 O(n) 时间了。因此，这个算法是最优的。

Answer 2

假设你的方法。索引从 0 开始。

一般表示：

• end_1 = floor(N/2) 第一部分的边界（含）。

迭代时表示：

• i 第一部分索引，j 第二部分索引，
• 到此为止的最佳解决方案sol(i,j)（使用前面的算法），
• 在 (i,j) 点后仍有待最佳配对的对，即来自 (i+1,j+1)向前rem(i,j)（可以用后面的算法计算），
• 最终最优解可以表示为任意点的函数为sol(i,j) + rem(i,j).

观察 #1：当从前面做算法时，[0, i] 范围内的所有点都被使用，[end_1+1, j] 范围内的一些点未被使用（我们跳过 a(j) 不够大）。从后面做算法时，一些 [i+1, end_1] 点没有被使用，并且所有 [j+1, N] 点都被使用（我们跳过 a(i) 不够小）。

观察 #2：rem(i,j) >= rem(i,j+1)，因为 rem(i,j) = rem(i,j+1) + M，其中 M 可以是 0 或 1 取决于我们是否可以将 a(j) 与 [i+1, end_1] 范围内的一些未使用元素配对。

参数（自相矛盾）： 让我们假设 2*a(i) <= a(j) 并且不配对 a(i) 和 a(j) 至少给出同样好的最终结果解决方案。根据算法，我们下一步将尝试配对 a(i) 和 a(j+1)。自：

• rem(i,j) >= rem(i,j+1)（见上文），
• sol(i,j+1) = sol(i,j)（因为我们没有配对 a(i) 和 a(j)）

我们得到 sol(i,j) + rem(i,j) >= sol(i,j+1) + rem(i,j+1) 这与假设相矛盾。