如何证明贪心算法进行数字划分？

Question

划分问题（或number partitioning1)是一个任务，它决定一个给定的正整数多集S是否可以划分为两个子集S1和S2，使得S1中的数之和等于S2中的数之和。

这个问题有一个贪婪的算法：

解决这个问题的一种方法是贪婪算法，它模仿孩子们为游戏选择队伍的方式，将数字按降序进行迭代，将每个数字分配到和较小的子集中。这种方法的运行时间为O（n log n）。当集合中的数字大小与其基数大小差不多或更小时，这种启发式在实践中很好地工作，但不能保证产生尽可能好的分区。例如,给定集合S={4,5,6,7,8}作为输入,该贪婪算法将S划分为子集{4,5,8}和{6,7}；但是，S有一个完全平衡的分区，分为子集{7,8}和{4,5,6}。

但是，我不知道如何证明这个启发式在实践中很好地工作，当集合中的数字大小与基数大小差不多或更小时。有人能帮忙吗？

Answer 1

这一主张并不确切；这只是说，如果多集的元素不比它的基数大多少，那么启发式通常会给出正确的答案，除非你注意找出它不知道的情况。所以这一说法不能被真实地“证明”。

此外,有许多不同的方法可以使索赔精确；并不是所有这些方法都必然导致一个真正的主张。所以你不能只做精确的陈述然后再证明。

然而，如果你读一下你引用的那一段之后的段落，它提供了一个相关的主张，这个主张是精确的，而且（根据文章）是正确的，即如果多集S可以被划分为两个和都≤OPT，那么这个贪婪算法将把它划分为两个和都≤/OPT，的多集。但是，这一索赔与原索赔并不相同；它为启发式的错误程度设定了一个上限，但它并不保证它永远都是正确的，它也没有提到元素的值。