寫一個程序確定是否可以以這樣的方式使得它們的和是相等的

Question

實施例形成的數字兩組：

輸入：3,6，3 輸出：真（因爲3 + 3 = 6）

輸入：3，2，6,4 輸出：假（因爲沒有結合，會造成平等）

輸入：4,7，3，6 輸出：真（因爲4 + 6 = 7 + 3）

你們可以給我一個想法如何編碼？ 我已經開始如何編碼，但我很困惑如何添加數字和比較他們

Answer 1

我會解釋一個人如何在不知道魔術詞的情況下如何工作（如「分區問題」 ，「動態編程」等），以查閱一些大的答案書（如維基百科）。

如果您從輸入中獲取最大未使用數字的一個實例並將其分配給您的兩個組中的一個，那麼您已將問題簡化爲一個較小的實例（一般化版本）問題。

廣義的問題是，你可以將輸入數字分成兩組，使得兩組之和的差值是一個特定的非負整數？

比方說，我們的輸入數字是4，3，2，1，我們需要建立兩個組，使各羣體的款項之間的差額爲0

我們給予4組之一，在這個特殊情況下，哪個組別並不重要。

現在我們剩餘的輸入數字是3,2,1，並且忽略我們已經處理的4個數字，我們需要將這三個數字分成兩組，以便組之間的總和之差爲4。將平衡我們通過將4分配給其中一個組而創建的兩個組之間的差異）。如所承諾的，這是原始類型問題的較小實例。

困難在於，有時候，比如說有5,5,4,3,3（例如在維基百科中發現的「分區問題」），下一個數字需要進入哪個組並不明顯。如果你跟蹤你所做的事情，那麼當你發現你的最新嘗試失敗時，你可以回來（「回溯」）並嘗試另一種方式。

5, 5, 4, 3, 3 {} {} 
    5, 4, 3, 3 {5} {} 
     4, 3, 3 {5} {5} 
     3, 3 {5, 4} {5} 
      3 {5, 4} {5, 3} 
       {5, 4} {5, 3, 3} NO - backtrack 
       {5, 4, 3} {5, 3} NO - backtrack 
      3 {5, 4, 3} {5} 
       {5, 4, 3} {5, 3} NO - already tried - backtrack 
       {5, 4, 3, 3} {3} NO - backtrack 
     3, 3 {5} {5, 4} NO - symmetric to what we already tried - backtrack 
     4, 3, 3 {5, 5} {} 
     3, 3 {5, 5} {4} 
      3 {5, 5} {4, 3} 
       {5, 5} {4, 3, 3} YES 

我們能很快得到答案嗎？那麼，這不是被問到的問題，但鑑於回溯的複雜性，很自然地問。答案的結果是，不，即使我們有世界歷史上最聰明的人爲我們工作。從來沒有人發現過一種方法可以保證快速執行，無論我們給出這種問題的實例如何。也許我們可以在這些問題的許多例子中做得很好，但總的來說，一般來說，做這類事情的程序註定會變慢。

Answer 2

這是分區問題，它是NP完全的。儘管如此，還是有一個可以使用的動態編程解決方案。請參閱維基百科文章。

http://en.wikipedia.org/wiki/Partition_problem

Answer 3

public class Weirdie { 
private boolean calculate(int[] array) { 
    boolean match = false; 
    List<Integer> list = new ArrayList<Integer>(); 
    int length = array.length; 
    for(int i=0;i<length;i++) { 
     for(int j=i+1;j<length;j++) { 
      int sum = array[i] + array[j]; 
      if(list.contains(sum)) { 
       match = true; 
       break; 
      } else { 
       list.add(sum); 
      } 
     } 
     if(match) { 
      break; 
     } 
    } 
    return match; 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] array = { 3, 6, 3, 4, 8}; 
    int[] array2 = { 3, 2, 6, 4}; 
    int[] array3 = { 4, 7, 3, 6 }; 
    Weirdie w = new Weirdie(); 
    System.out.println(w.calculate(array)); 
    System.out.println(w.calculate(array2)); 
    System.out.println(w.calculate(array3)); 
} 

}

實際上我仍然混淆與requirement.As您的描述，數第1組{3,6,3}將輸出由於3 + 3 = 6真。你說數字組2 {3,2,6,4}會輸出false，但顯然2 + 4 = 6也符合你的條件。用你的第三個數字組，我認爲數字組1輸出真的原因是3 + 6 = 6 + 3。

Answer 4

要確定是一個陣列可分成兩個相等的求和陣列，我們還可以發現，其具有整個陣列的總和的一半的子集。

對於e.g：輸入：4,7，3，6

我們應該找到的子集，其總和== 10，這是一個簡單DP概率。

公共靜態布爾isSubset（INT []一，INT總和，INT N）{

if(sum == 0) 
    return true; 
    if(n<0) 
    return false; 
return isSubset(a, sum-a[n], n-1) || isSubset(a, sum, n-1); 
} 

Answer 5

OK！只是用蠻力計算，我檢查每個可能的選擇

int[] numbersArray = new int[10]; 
int sum = 0; 

for(int j = 0; j < numbersArray.lenght;j++) // sum 
    sum += numbersArray[j]; 



for(int i = 0; i < numbersArray.lenght;i++) 
{ 
    int numChecking = numbersArray[i]; // right half .. 

    if((sum-numChecking) == numChecking) 
    return true; 

} 
return false; 

//我沒有測試過，但是，這將檢查所有可能的1個值..