算法 - 找到兩個數組的總和之間的最小減法

我現在正在打獵並做許多算法練習。這裏是我的問題：算法 - 找到兩個數組的總和之間的最小減法

給定兩個數組：一個和b具有相同的長度，主題是讓|總和（一）-sum（B）|通過交換a和b之間的元素。

這是我雖然：

基於該思想上述我得到了以下的代碼：

Delt = sum(a) - sum(b); 
done = false; 
while(!done) 
{ 
    done = true; 
    for i = [0, n) 
    { 
     for j = [0,n) 
     { 
      x = a[i]-b[j]; 
      change = x*(Delt-x); 
      if(change >0) 
      { 
       swap(a[i], b[j]); 
       Delt = Delt - 2*x; 
       done = false; 
      } 
     } 
    } 
}

然而，沒有任何人有一個更好的解決方案？如果你有，請告訴我，我會非常感激你！

來源

2011-10-02 Flybywind

你的問題等同於「給定一個長度爲2 * n和sum（a）= 2 * S的數組a，在數組中找到正好n個元素，其總數儘可能接近S. 「 –

這看起來像變相揹包問題。 –

@ n.m。更像分區問題，正如馬克提到的......但還有一個額外的限制：相同數量的元素... – amit

這個問題基本上是Partition Problem的優化問題，並帶有額外的相等部分約束。我會證明添加這個約束並不會使問題更容易。

NP-Hardness證明：
假設有在多項式時間內解決這個問題的算法A，我們可以在多項式時間內解決Partition-Problem。

Partition(S): 
for i in range(|S|): 
    S += {0} 
    result <- A(S\2,S\2) //arbitrary split S into 2 parts 
    if result is a partition: //simple to check, since partition is NP. 
    return true. 
return false //no partition

正確性：
如果有一個分區表示爲（S1，S2）假設S2具有以上的元素]，上迭代| S2 | - | S1 | [即當添加| S2 | - | S1 |時零。對A的輸入將控制足夠的零，所以我們可以返回兩個相等長度的數組：S2，S1 + {0,0，...，0}，這將是S的分區，並且該算法將產生真實。
如果算法得出結果，並且迭代k，我們有兩個數組：S2，S1，具有相同數量的元素和相等的值。通過從數組中刪除k零，我們得到一個分區到原始S，所以S有一個分區。

多項式：
承擔A需要P(n)時間，我們生產的需要n*P(n)時間，這也是多項式算法。

結論：
如果這個問題是在多項式時間solveable，所以確實的Partion-問題，因此P = NP。基於此：這個問題是NP-Hard。

因爲這個問題是NP-Hard，對於一個確切的解決方案，您可能需要一個指數算法。其中之一是簡單backtracking [I離開它作爲練習向讀者實施回溯溶液]

EDIT：如通過@jpalecek提及：通過簡單地創建一個還原：S->S+(0,0,...,0) [k次0]，一個可以直接通過還原來證明NP-硬度。多項式是微不足道的，並且正確性與上述分區的正確性證明非常相似：[如果存在分區，則可以添加'平衡'零;另一個方向是簡單地修剪那些零]

來源

2011-10-02 08:58:23 amit

我相信你的縮進錯了 - 你爲什麼要執行結果<-A（S \ 2，S \ 2）'n次？順便說一句，你寫的不是多項式約簡，我們用它來證明NP硬度。 – jpalecek

@jpalecek：我每一步都執行一次'A（S/2，S/2）'，並檢查一個可能的解決方案，其中'k'是迭代的數量。我在這裏沒有使用約簡，我證明如果存在這樣的算法，P = NP，這相當於說這個算法是NP-Hard。 [因爲它顯然是NP，並且如果P = NP，那麼P = NP = NP-Complete] – amit

問題在於你必須使用縮減來證明NP-硬度，因爲NP-硬度是根據縮減定義的。你已經證明的是'P^A'中的'Partition \'，但它不遵循（至少不是直接）A是NP完整的。而且，如果你只添加了所有的零並且問了一次，它也會起作用，並且你會減少。 – jpalecek

只是一個評論。通過所有這些交換，你可以基本上安排兩個陣列的內容。所以這個值在哪個數組中並不重要。

不能這樣做在我的腦海中，但我很確定有一個建設性的解決方案。我想如果你先排序他們，然後按照一些規則處理它們。沿線的一些東西If value > 0 and if sum(a)>sum(b) then insert to a else into b

來源

2011-10-02 08:58:31 bdecaf

算法 - 找到兩個數組的總和之間的最小減法

回答

相關問題