子集總和的變體

Question

我通讀了所有子集總和主題，並且仍存在實現以下問題的算法問題。

給定N個整數數組A（N < = 20）其中

• A [1] < = 20
• 值不必是唯一的

和整數K（K < = 20）。

規則：

• 等於k陣列項都「覆蓋」與K.
• 如果兩個或更多陣列數的總和等於K，這些數字也包括在內。
• 數組中的每個數字只能被覆蓋一次。

例：

N = 6，整數：1，1，2，3，4，5

K = 4

可能的覆蓋範圍：

1. 覆蓋範圍
   • 4被覆蓋。
   • 1，1，2被覆蓋爲1 + 1 + 2 = 4。
2. 覆蓋
   • 4被覆蓋。
   • 1,3覆蓋爲1 + 3 = 4。

K = 5

可能的覆蓋範圍：

1. 覆蓋
   • 5被覆蓋。
   • 1,1,3被覆蓋爲1 + 1 + 3 = 5。
2. 覆蓋
   • 5被覆蓋。
   • 1,4被覆蓋爲1 + 4 = 5。
   • 2,3被覆蓋爲2 + 3 = 5。

目標：

對於給定的陣列A和整數K，找到所有可能的 「覆蓋範圍」。我需要所有覆蓋範圍，不僅覆蓋大部分數組項目。

我曾嘗試用兩種方法：

1. 香檳力算法。 檢查所有可能尺寸的所有可能的子集，但即使只有10個數字也需要太多時間。我需要它在不超過500毫秒內完成。
2. 首先，我按降序排列數組。然後，對於每個可能數量的子款項，我創建「槽」。我通過陣列環，並把數字在以下等規則的槽：在槽
   • 穿戴數如果其總和變爲等於K.
   • 穿戴數目在具有所有時隙的至少總和的插槽。
   • 把數字放在給出所有插槽的K的壁櫥總和的插槽中。

那麼，第二種方法的工作原理和工作速度很快。但是我發現沒有找到一些coverage的場景。

如果有人提出解決這個問題的想法，我將不勝感激。

我希望我解釋得很好。

謝謝。

Answer 1

我沒有現成的答案，但我建議看看'Bin裝箱問題'在這裏可能有用。

的主要問題是找出所有可能的和給數K.那麼試試這個：

Collection All_Possible_Sums_GivingK; 

find_All_Sums_Equal_To_K(Integer K, Array A) 
{ 
    /* this function after finding result 
    add it to global Collection AllPossibleSumsGivingK; */ 
    find_All_Elements_Equal_To_K(Integer K, Array A); 

    Array B = Remove_Elements_Geater_Or_Equal_To_K(Integer K, Array A); 

    for all a in A { 
     find_All_Sums_Equal_To_K(Integer K-a, Array B-a) 
    } 
} 

Answer 2

我修改這從以前的答案我給了一個不同的子集和變型：https://stackoverflow.com/a/10612601/120169

我我在這裏用上面的數字在K = 8的情況下運行它，我們在兩個不同的地方爲兩個「coverage」中的一個重複使用1。讓我知道它是如何爲你工作的。

public class TurboAdder2 { 
    // Problem inputs 
    // The unique values 
    private static final int[] data = new int[] { 1, 2, 3, 4, 5 }; 
    // counts[i] = the number of copies of i 
    private static final int[] counts = new int[] { 2, 1, 1, 1, 1 }; 
    // The sum we want to achieve 
    private static int target = 8; 

    private static class Node { 
     public final int index; 
     public final int count; 
     public final Node prevInList; 
     public final int prevSum; 
     public Node(int index, int count, Node prevInList, int prevSum) { 
      this.index = index; 
      this.count = count; 
      this.prevInList = prevInList; 
      this.prevSum = prevSum; 
     } 
    } 

    private static Node sums[] = new Node[target+1]; 

    // Only for use by printString and isSolvable. 
    private static int forbiddenValues[] = new int[data.length]; 

    private static boolean isSolvable(Node n) { 
     if (n == null) { 
      return true; 
     } else { 
      while (n != null) { 
       int idx = n.index; 
       // We prevent recursion on a value already seen. 
       // Don't use any indexes smaller than lastIdx 
       if (forbiddenValues[idx] + n.count <= counts[idx]) { 
        // Verify that none of the bigger indexes are set 
        forbiddenValues[idx] += n.count; 
        boolean ret = isSolvable(sums[n.prevSum]); 
        forbiddenValues[idx] -= n.count; 
        if (ret) { 
         return true; 
        } 
       } 
       n = n.prevInList; 
      } 
      return false; 
     } 
    } 

    public static void printString(String prev, Node n, int firstIdx, int lastIdx) { 
     if (n == null) { 
      printString(prev +" |", sums[target], -1, firstIdx); 
     } else { 
      if (firstIdx == -1 && !isSolvable(sums[target])) { 
       int lidx = prev.lastIndexOf("|"); 
       if (lidx != -1) { 
        System.out.println(prev.substring(0, lidx)); 
       } 
      } 
      else { 
       while (n != null) { 
        int idx = n.index; 
        // We prevent recursion on a value already seen. 
        // Don't use any indexes larger than lastIdx 
        if (forbiddenValues[idx] + n.count <= counts[idx] && (lastIdx < 0 || idx < lastIdx)) { 
         // Verify that none of the bigger indexes are set 
         forbiddenValues[idx] += n.count; 
         printString((prev == null ? "" : (prev + (prev.charAt(prev.length()-1) == '|' ? " " : " + ")))+data[idx]+"*"+n.count, sums[n.prevSum], (firstIdx == -1 ? idx : firstIdx), idx); 
         forbiddenValues[idx] -= n.count; 
        } 
        n = n.prevInList; 
       } 
      } 
     } 
    } 

    public static void main(String[] args) { 
     for (int i = 0; i < data.length; i++) { 
      int value = data[i]; 
      for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) { 
       for (int newsum = sum+1; newsum <= target; newsum++) { 
        if (sums[newsum - sum] != null) { 
         sums[newsum] = new Node(i, count, sums[newsum], newsum - sum); 
        } 
       } 
      } 
      for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) { 
       sums[sum] = new Node(i, count, sums[sum], 0); 
      } 
     } 
     printString(null, sums[target], -1, -1); 
    } 
}