algorithm - 子集求和算法

Question

我正在解决这个问题:

The Subset Sum problem takes as input a set X = {x1, x2 ,…, xn} of n integers and another integer K. The problem is to check if there exists a subset X' of X whose elements sum to K and finds the subset if there's any. For example, if X = {5, 3, 11, 8, 2} and K = 16 then the answer is YES since the subset X' = {5, 11} has a sum of 16. Implement an algorithm for Subset Sum whose run time is at least O(nK).

通知复杂性 O(nK) .我认为动态规划可能会有所帮助。

我找到了一个指数时间算法，但它没有帮助。

有人可以帮我解决这个问题吗？

Answer 1

Subset Sum 是我在 Macalester 学到的第一个 NP 完全问题。这个问题被查看了 36000 多次，但我没有看到足够的答案来详细解释算法的逻辑。所以我想我会尝试这样做。

假设:

为了简单起见，我首先假设输入集 X仅包含正整数和 k是积极的。但是，我们可以调整算法来处理负整数和 if k 的情况。是否定的。

逻辑:

这个算法的关键还是真的任何 DP 问题都是分解问题并简单地从基本案例开始。 然后我们可以使用我们知道的一些知识建立在基本案例的基础上:

我们知道如果设置 X为空，那么我们无法求和为 k 的任何值.

如一套X包含 k那么它有一个子集和到 k .

我们知道如果集合 x1 的一个子集谁是X的子集总和到 k1然后 X将有一个总和为 k1 的子集即 x1 .

我们有一套 X = {x1, x1, x3, ......., xn, xn+1} .我们知道它有一个子集和到 k1如果 x1 = {x1, x1, x3, ......., xn}有一个子集和到 k - k1 .

举例说明 1,2,3,4:

这很容易。如果您有一个空集 {}。你不能有一个子集
你不能有任何子集总和。

一套X = {4}有一个子集和为 4，因为 4 它本身是集合的一部分

说你有一套 x1 = {1,3,5}谁是集合的子集X = {1,3,5,2,8} .如果 x1有一个子集和到 k1 = 8那么这意味着 X也有一个子集和为 8 因为 x1是 X 的子集

说你有一套 X = {1,3,5,2,19}我们想知道它的子集总和是否为 20。它确实是一种方法，可以知道它是否是 x1 = {1,3,5,2}可以总和为 (20 - 19) = 1。由于 x1 的子集总和为 1，那么当我们将 19 添加到集合 x1 时
我们可以用这个新数字 1 + 19 = 20 来创建我们想要的总和 20。

动态构建矩阵
凉爽的!现在让我们利用上述四种逻辑并从基本案例开始构建。我们将构建一个矩阵 m .我们定义:

矩阵m有 i+1行和 k + 1列。

矩阵的每个单元格都有值 true或 false .

m[i][s] 返回 true 或 false 以指示此问题的答案:“使用数组中的前 i 项，我们能否找到 s 的子集和？” m[i][s]返回 true对于是和 false对于没有

(注意维基百科的答案或大多数人构建了一个函数 m(i,s) 但我认为矩阵是一种理解动态规划的简单方法。当我们在集合或数组中只有正数时它工作得很好。但是函数路由更好，因为您不必处理超出范围的索引，匹配数组的索引并求和到矩阵.....)

让我们使用一个例子来构建矩阵:

X = {1,3,5,2,8}
k = 9

我们将逐行构建矩阵。我们最终想知道单元格 m[n][k] 包含 true或 false .

第一行:
逻辑1.告诉我们矩阵的第一行应该都是false .

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1|
2|
3|
4|
5|

第二排及以上:
然后对于第二行或以上，我们可以使用逻辑 2,3,4 来帮助我们填充矩阵。

逻辑 2 告诉我们 m[i][s] = (X[i-1] == s)记住 m[i] 指的是 X 中的第 i 个项目，即 X[i-1]

逻辑 3 告诉我们 m[i][s] = (m[i-1][s])这是看上面的单元格方向。

逻辑 4 告诉我们 m[i][s] = (m[i-1][s - X[i-1]])这是查看 X[i-1] 单元格上方和左侧的行。

如果其中任何一个是 true然后 m[i][s]是 true否则 false .所以我们可以将 2,3,4 改写成 m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])
使用上述这些逻辑来填充矩阵 m .在我们的示例中，它看起来像这样。

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1| F T F F F F F F F F
2| F T F T T F F F F F 
3| F T F T T T T F T T
4| F T T T T T T T T T 
5| F T T T T T T T T T

现在使用矩阵来回答您的问题:

看 m[5][9]这是原始问题。使用前 5 个项目(即所有项目)我们可以找到一个子集总和为 9 (k) 吗？答案由 true 的单元格表示

这是代码:

import java.util.*;

public class SubSetSum {

    public static boolean subSetSum(int[] a, int k){

        if(a == null){
            return false;
        }

        //n items in the list
        int n = a.length; 
        //create matrix m
        boolean[][] m = new boolean[n + 1][k + 1]; //n + 1 to include 0, k + 1 to include 0 

        //set first row of matrix to false. This also prevent array index out of bounds: -1
        for(int s = 0; s <= k; s++){
            m[0][s] = false;
        }

        //populate matrix m
        for(int i = 1; i <= n; i++){
            for(int s = 0; s <= k; s++){    
                if(s - a[i-1] >= 0){ //when it goes left we don't want it to go out of bounds. (logic 4)
                    m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]]); 
                } else {
                    m[i][s] = (m[i-1][s] || a[i-1] == s);
                }       

            }
        }

        //print matrix
        print(m);

        return m[n][k];

    }

    private static void print(boolean[][] m){
        for(int i = 0; i < m.length; i++){
            for(int j = 0; j < m[i].length; j++){
                if(m[i][j]){
                    System.out.print("T");
                } else {
                    System.out.print("F");
                }           
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args){
        int[] array = {1,3,5,2,8};
        int k = 9;

        System.out.println(subSetSum(array,k));

    }
}

构建矩阵 m取 O((n+1)(k+1)) 即 O(nk)。看起来它应该是多项式的，但它不是!它实际上是伪多项式。阅读它 here

同样，这仅在输入仅包含正数时才有效。您可以轻松调整它以使用负数。矩阵仍然有 n+1 行，但 B - A + 1列。哪里B是上限和 A是下限(+1 包括零)。矩阵仍然是你必须偏移 s与下限。

从头到尾解释文本上的 DP 问题非常困难。但我希望这能帮助那些试图理解这个问题的人。

请注意，在上面的示例中，DP 表的行已排序。不一定是这样。

这是问题案例的 DP 表，即给定一组 {5, 3, 11, 8, 2}。为简洁起见，我省略了错误值。

┌─────────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ (index) │  0   │  2   │  3   │  5   │  7   │  8   │  10  │  11  │  13  │  14  │  15  │  16  │
├─────────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│    0    │ true │      │      │      │      │      │      │      │      │      │      │      │
│    5    │ true │      │      │ true │      │      │      │      │      │      │      │      │
│    3    │ true │      │ true │ true │      │ true │      │      │      │      │      │      │
│    11   │ true │      │ true │ true │      │ true │      │ true │      │ true │      │ true │
│    8    │ true │      │ true │ true │      │ true │      │ true │ true │ true │      │ true │
│    2    │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │
└─────────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

下面是一个 JavaScript 实现，它将输出目标集 {5, 11}:

var subSetSum = function(input, sum) {

    let y = input.length;
    let x = sum;

    if(input.length === 0) return 0;

    let d = [];

    //fill the rows
    for (let i = 0; i <= y; i++) {
      d[i] = [];
      d[i][0] = true;
    }
    
    for (let j = 1; j <= y; j++) { //j row
      for (let i = 1; i <= x; i++) { //i column
      let num = input[j-1];
        if(num === i) {
          d[j][i] = true;
        } else if(d[j-1][i]) {
          d[j][i] = true;
        } else if (d[j-1][i-num]) {
          d[j][i] = true;
        }
      }
    }
    
    //console.table(d); //uncomment to see the table
    if(!d[y][x]) return null;

    let searchedSet = [];
    for(let j=input.length, i=sum; j>0 && i != 0; j--) {
      if(input[j-1] !== i) {
        while(d[j-1][i]) { // go up
          j--;
        }
      }
      searchedSet.push(input[j-1]);
      i = i-input[j-1];
    }

    return searchedSet;
};

console.log('searched set:'+ JSON.stringify(subSetSum([5, 3, 11, 8, 2], 16)));