平衡分区贪婪方法

Question

我正在 en.wikipedia 和 MIT DP 笔记集（问题 7） 中查看平衡分区问题。

该问题基本上要求将给定的数字数组划分为 2 个子集（S1 和 S2），使得数字之和之间的绝对差为 S1 且 S2

|sum(S1) - sum(S2)|

需要最小。我不明白的一件事是为什么没有人建议贪婪的方法：

def balanced_partition(lst):
    idx = 0
    S1 = 0
    S2 = 0
    result_partition=[None]*len(lst)
    while idx < len(lst):
        new_S1 = S1 + lst[idx]
        new_S2 = S2 + lst[idx]
        if abs(new_S1 - S2) < abs(new_S2 - S1):
            result_partition[idx] = 1
            S1 = new_S1
        else:
            result_partition[idx] = 2
            S2 = new_S2
        idx += 1
    print("final sums s1 = {S1} and s2 = {S2} ".format(S1=S1, S2=S2))
    return result_partition

我的方法有什么问题吗？它似乎通过了我能想到的所有测试用例。

Answer 1

简单的反例是

[1,1,1,1,1,1,6]

。贪心的方法会在两个集合之间分散，而最优解是

[1,1,1,1,1,1]

，

[6]

。

Answer 2

您的实施和方法没有任何问题。但是，如果您考虑这个特定问题中的所有子集，您可能会找到比贪婪输出更好的答案。即使在您共享的维基页面中也有一些示例。

您可能已经知道这两种方法之间的区别。尽管贪心算法总是会给你一个相当好的结果，非常接近或可能等于最好的结果，但你必须考虑所有选项才能确定。动态规划方法以某种方式检查所有可能的子集。由于它保存了先前计算的子问题的结果，因此基本上比暴力破解更快。

问题是何时使用贪婪或动态规划方法。我做过一些竞争性编程，当我看到DP问题（分区、子集和、背包等问题）时，我有时会立即想出一个贪婪的解决方案，因为大多数时候它们更明显。人们在日常生活中无时无刻不在使用贪婪的方法。在实施之前，我会用示例测试我的算法，如果我说服自己这是正确的方法，我就会实施它。在某种程度上，这有点直观。

如果你发现一个测试用例应该有更好的答案，很可能意味着你必须找到一个 DP 解决方案。如果你从法官系统中得到 WA，这意味着你还没有找到好的测试用例，但是没关系，你不必找到确切的测试用例，因为它不会帮助你找到更好的解决方案。