平衡分区贪婪方法

-1

我在寻找平衡分区问题here和here (problem 7)。平衡分区贪婪方法

该问题基本上要求将给定的数字数组分割成2个子集（S1和S2），使得数字之和的绝对差值为S1和S需要最小。有一件事我不明白的是为什么没有人提出贪婪的方法：

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

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

来源

2017-03-06 kmad1729

“似乎通过了大部分测试用例”。所以它失败了一些测试用例？这不是回答你的问题吗？ –

大部分测试用例我的意思是我找不到反对贪婪方法的任何争论，我自己也无法（出现）/发现负面测试用例。编辑我的问题。 – kmad1729

你是如何搜索负面测试用例的？几乎每个排序的列表都是您的方法的最佳反例（例如：[1,2,3]）。 –

简单的反例是[1,1,1,1,1,1,6]。贪婪的方法将分散在两组之间，而最优方案是[1,1,1,1,1,1]，[6]。

来源

2017-03-07 00:24:27

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

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

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

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

来源

2017-03-07 00:25:28 hikmathaji

平衡分区贪婪方法

回答

相关问题