達到一個目標整數

我有一個隨機長度的數組，充滿隨機整數。爲了簡單起見，它們從最高到最低排序。達到一個目標整數

我也有一個目標隨機整數。

我需要得到所有總和大於或等於目標的組合，而不使用不必要的數字。鑑於這個例子：

nums = [10, 6, 5, 3, 2, 1, 1] 

target = 8

我想這樣的輸出：

10 (10 is higher or equal to 8, so there's no need to sum it) 

6+5 

6+3 

6+2 

6+1+1 

5+3 

5+2+1 

5+2+1 (Note that this result is different from the previous since there are 2 1s)

我已經嘗試了很多的遞歸策略，但我無法找到一個正確的答案。不需要特定的語言，僞代碼是受歡迎的。

編輯：過帳代碼

private static boolean filtrar(final CopyOnWriteArrayList<Padre> padres) { 
     if (sum(padres) < TARGET) { 
      return false; 
     } 
     int i; 
     for (i = padres.size(); i >= 0; i--) { 
      if (!filtrar(copiaPadresSinElemento(padres, i-1))) { 
       break; 
      } 
     } 
     // Solución óptima, no se puede quitar nada. 
     if (i == padres.size()) { 
      print(padres); 
     } 
     return true; 
    } 

    private static int sum(final CopyOnWriteArrayList<Padre> padres) { 
     int i = 0; 
     for (final Padre padre : padres) { 
      i += padre.plazas; 
     } 
     return i; 
    } 

    private static void print(final CopyOnWriteArrayList<Padre> padres) { 
     final StringBuilder sb = new StringBuilder(); 
     for (final Padre padre : padres) { 
      sb.append(padre); 
      sb.append(", "); 
     } 
     final String str = sb.toString(); 
     System.out.println(str); 
    } 

    private static CopyOnWriteArrayList<Padre> copiaPadresSinElemento(
      final CopyOnWriteArrayList<Padre> padres, final int i) { 
     final CopyOnWriteArrayList<Padre> copia = new CopyOnWriteArrayList<Padre>(); 
     for (int e = 0; e < padres.size(); e++) { 
      if (e != i) { 
       copia.add(padres.get(e)); 
      } 
     } 
     return copia; 
    }

帕德瑞是一個簡單的對象，其包含每個號碼的名稱。 Padre.plazas是數字。

陣列現在的問題是[6,4,4,4,3,3,3]，目標是8

來源

2012-10-17 razielsarafan

這似乎是相當類似http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of - 數量達到一個給定的總和 – Hans

這是有點類似，但它不是和我想要得到的一樣，如果它們相等或更大。我覺得這個問題要困難得多。 – razielsarafan

我覺得像這樣的工作：

function filter(array, target): Boolean{ //assumes array is sorted in descending order 
    if(sum(array) < target) return false; 
    for(i = array.length-1; i>=0; --i){ 
    if(! filter(array.createCopyRemovingElementAt(i), target)) break; 
    } 
    if(i==array.length-1) print(array); // solution is "optimal": could not remove a single number 
    return true; 
}

來源

2012-10-17 08:50:26 Eduardo

但是，即使它不是最佳解決方案，它也會打印陣列。我想只打印最佳的。 – razielsarafan

我現在明白了。將其更改爲僅打印最佳解決方案 – Eduardo

執行此操作時出現StackOverflowError :( – razielsarafan

低效的解決方案：複雜度= O（（2^N）* N）

for i = 0 to 2^size-of-array 
do 
    sum = 0 
    for j = 0 to n-1 
    do 
    if(jth bit in i is 1) 
    then 
     sum+=array[j] 
     fi 
    done 

    if(sum>=target) 
    print the number i (uniquely identifies the set of numbers) 
done

來源

2012-10-17 08:59:48

達到一個目標整數

回答

相關問題