適合數字的最佳方法

我有以下一組整數{2,9,4,1,8}。我需要把這個集合分成兩個子集，以便集合的總和分別爲14和10。在我的例子中，答案是{2,4,8}和{9,1}。我不尋找任何代碼。我很確定必須有一個標準的算法來解決這個問題。由於我沒有成功搜索並找到自己，我在這裏發佈了我的查詢。那麼解決這個問題最好的辦法是什麼？適合數字的最佳方法

我的嘗試是這樣的...

public class Test { 
    public static void main(String[] args) { 
     int[] input = {2, 9, 4, 1, 8}; 
     int target = 14; 
     Stack<Integer> stack = new Stack<>(); 
     for (int i = 0; i < input.length; i++) { 
      stack.add(input[i]); 
      for (int j = i+1;j<input.length;j++) { 

       int sum = sumInStack(stack); 

       if (sum < target) { 
        stack.add(input[j]); 
        continue; 
       } 

       if (target == sum) { 
        System.out.println("Eureka"); 
       } 

       stack.remove(input[i]); 
      } 

     } 
    } 

    private static int sumInStack(Stack<Integer> stack) { 
     int sum = 0; 
     for (Integer integer : stack) { 
      sum+=integer; 
     } 
     return sum; 
    } 
}

我知道這種做法甚至還沒有接近解決問題

來源

2016-12-25 Tiny Rick

這就是多重揹包問題。 https://en.wikipedia.org/wiki/Knapsack_problem或者裝箱問題。這取決於你還沒有指定的額外約束，比如是否需要使用所有元素。 –

@ErwinBolwidt所有元素都應該在最後使用。我說我的問題有2個子集的結果。我需要一個通用算法來將父集合分成n個子集，其中每個子集合總計達到某個指定的數目。 –

我需要這一套分爲兩個子集，使之和分別爲14和10。

如果子集必須求和某些值，那麼最好是整個集合的總和就是這些值的總和，即在你的例子中爲14 + 10 = 24。如果你只需要找到兩個子集，那麼問題就不是很困難 - 找到與其中一個值相加的任何子集，並且集合的其餘元素必須與另一個值相加。

對於例如設置你給，{2,9,4,1,8}，你說的答案是{9,1}, {2,4,8}，但是請注意，這不是唯一的答案;還有{2,8}, {9,4,1}。

來源

2016-12-25 05:43:00 Caleb

從哪個角度看「不是很難」？如何以天真的方式實施，或者問題的時間複雜性？ :-) –

@Caleb是的。最好的解決辦法是列出所有可能的集合。感謝您指出 –

適合數字的最佳方法

回答

相關問題