平衡分區貪婪方法

-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

平衡分區貪婪方法

回答

相關問題