匹配数字的贪心算法
Greedy Algorithem for matching numbers
我们有一组 'S'，其中包含 2n 只袜子。组中的每只袜子都有一种颜色。
颜色由正实数表示。 [c : S -> R(+)]
同组2只袜子同色是可以的。
-我们这样定义一双袜子 (a,b) 的 "Punishment"：
P(a,b) = |c(a)-c(b)|。 （也就是说2只同色袜子的"punishment"为0）
我需要描述一个贪心算法，它将一组 S 和 returns 一组包含袜子的组 A 作为输入（来自 S 的每只袜子，正好在 A 中一次）和总结惩罚将是最小。
[总结惩罚=>该组所有对的惩罚总和]
而且我需要证明算法是正确的。
我无法证明我的算法是正确的，
我根据袜子的数值颜色值对袜子进行排序，每次都从 S 中挑选第一只。
我试图用归纳法来证明它，但我不知道我需要如何做最优组中的 'switching' 部分。
所以你的算法是正确的:)
证明：
想象一下，我们对我们的问题有不同的解决方案，它比我们的解决方案更好（我们只是排序并匹配最接近的）。因此必须至少存在两对（a
1)a在区间(c,d)内，b不在区间或与其相似
（否则我们的解决方案中会有这对）。
现在让我们计算惩罚：惩罚是|a-b| + |c-d|
因为我们的 1) 我们可以考虑我们数字的顺序，例如：
2 : a < c < b < d
3 : a < c < d < b
4 : c < a < b < d
5 : c < a < d < b
两个在计算上几乎一样：
我们可以很容易地证明
例如在 (2) 中 |a-b| + |c-d| > |a-c| + |b-d|,
因为 a-b < a-c 并且 a < c < b 所以 |a-b| > |a-c|
c-d < b-d 且 c < b < d 所以 |c-d| > |b-d|
现在，如果发生这种情况，交换这些值会将此解决方案更改为更好的解决方案，这在我们的算法中看起来像:)
我们有一组 'S'，其中包含 2n 只袜子。组中的每只袜子都有一种颜色。 颜色由正实数表示。 [c : S -> R(+)] 同组2只袜子同色是可以的。
-我们这样定义一双袜子 (a,b) 的 "Punishment"： P(a,b) = |c(a)-c(b)|。 （也就是说2只同色袜子的"punishment"为0）
我需要描述一个贪心算法，它将一组 S 和 returns 一组包含袜子的组 A 作为输入（来自 S 的每只袜子，正好在 A 中一次）和总结惩罚将是最小。 [总结惩罚=>该组所有对的惩罚总和]
而且我需要证明算法是正确的。 我无法证明我的算法是正确的， 我根据袜子的数值颜色值对袜子进行排序，每次都从 S 中挑选第一只。 我试图用归纳法来证明它，但我不知道我需要如何做最优组中的 'switching' 部分。
所以你的算法是正确的:)
证明： 想象一下，我们对我们的问题有不同的解决方案，它比我们的解决方案更好（我们只是排序并匹配最接近的）。因此必须至少存在两对（a
1)a在区间(c,d)内，b不在区间或与其相似
（否则我们的解决方案中会有这对）。
现在让我们计算惩罚：惩罚是|a-b| + |c-d|
因为我们的 1) 我们可以考虑我们数字的顺序，例如：
2 : a < c < b < d
3 : a < c < d < b
4 : c < a < b < d
5 : c < a < d < b
两个在计算上几乎一样： 我们可以很容易地证明
例如在 (2) 中 |a-b| + |c-d| > |a-c| + |b-d|,
因为 a-b < a-c 并且 a < c < b 所以 |a-b| > |a-c| c-d < b-d 且 c < b < d 所以 |c-d| > |b-d|
现在，如果发生这种情况，交换这些值会将此解决方案更改为更好的解决方案，这在我们的算法中看起来像:)