與組合卡住問題

我遇到了問題w /我的程序。我提取了一組數據，我想測試一個特定數字是否有組合。例如，我有一個int數組，1 2 3 4 5，我想知道是否有7組合可能，並且它必須回答yes有3 + 4.與組合卡住問題

我發現我需要使用組合公式。所以我認爲外層循環可能像5C1..5C2..5C3..etc一樣，開始「取1」，然後「取2」，以找出所有可能的組合。問題是我堅持如何在實際代碼中實現這一點。

我對數學並不是很好，定義好的循環結構真的有幫助。

非常感謝！

2011-03-15 maru

下面是獲取所有可能的和從整數列表的方法：

public static void getAllPermutations(final List<Integer> data, 
    final Set<Integer> holder){ 

    if(data.isEmpty()){ 
     return; 
    } 
    final Integer first = data.get(0); 
    if(data.size() > 1){ 
     getAllPermutations(data.subList(1, data.size()), holder); 
     for(final Integer item : new ArrayList<Integer>(holder)){ 
      holder.add(first.intValue() + item.intValue()); 
     } 
    } 
    holder.add(first); 
}

用法：

List<Integer> data = Arrays.asList(1, 2, 3, 4, 5, 6); 
Set<Integer> permutations = new TreeSet<Integer>(); 
getAllPermutations(data, permutations); 
System.out.println(permutations);

輸出：

[1,2 2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21 ]

儘管該方案不會給你帶來的總和操作數，它將包括從1到1 + 2 + 3 + 4 + 5 + 6

來源

2011-03-15 10:27:04

正是我所需要的，非常感謝！ – maru 2011-03-15 11:09:32

一個快速和骯髒的解決方案可能是創建一個二維數組，其索引（在兩個維度中）是數組在數組中的位置，數值是組合。事情是這樣的：

//int i[] = { 1, 3, 5}, operation is 'add' 
//you have a 3x3 array here: 
//\ |1 3 5 <- the original values at their corresponding indices for quick reference, the array is the bottom right 3x3 matrix 
//--+------ 
//1 |2 4 6  
//3 |4 6 8 
//5 |6 8 10 

int[][] a = new int[3][3]; 
//in a loop fill the array

如果你現在要查找的組合爲6，你可以檢查所有值，並得到x和y指數是等於6的值（在這個例子中：0/2 ，1/1和2/0）。然後查找原始數組中那些索引處的數字（例如0/2 - > 1和5,1/1-> 3和3，2/0 - > 5和1）。

請注意，這是一種快速且非常不充分的方式（特別是對於較大的陣列），並且可能返回比您想要或需要的更多排列（對於操作add，0/2和2/0是相同的）。但是，這應該適用於許多可能的操作，例如對於x = 1，y = 5（結果：1）和x = 5，y = 1（結果：5），x ^y將是不同的。

來源

2011-03-15 10:24:24 Thomas

這是一個非常有創意的解決方案，tnx！ – maru 2011-03-15 11:07:35

什麼有一個簡單的僞多項式時間的動態規劃這個問題，首先確定是可能的富裕1然後爲2總和2我們有兩個選項，使用一個數組項目，或者使用以前創建的1加上新元素，就可以完成這個2維表格到富要求的數字：

bool findNode(int[] C , int givenNumber) { 
// compute the total sum 
int n = C.Length; 
int N = 0; 
for(int i = 0; i < n; i++) N += C[i]; 
// initialize the table 
T[0] = true; 
for(int i = 1; i <= N; i++) T[i] = false; 
// process the numbers one by one 
for(int i = 0; i < n; i++) 
    for(int j = N - C[i]; j >= 0; j--) 
    if(T[j]) T[j + C[i]] = true; 

return T[givenNumber]; 
}

這是O（n * Sum）。實際上已經足夠檢查到O(n*given_number)。

來源

2011-03-15 10:49:41

與組合卡住問題

回答

相關問題