子集和算法

Question

我正在研究这个问题:

该子集和问题需要输入一个组X = {x1, x2 ,…, xn}的n整数和另一个整数K.问题是,以检查是否存在一个子集X'的X,它的元素之和为K,并发现该子集,如果有任何.例如,如果X = {5, 3, 11, 8, 2}和K = 16那么答案是YES,因为该子集X' = {5, 11}具有的总和16.实现Subset Sum的算法,其运行时间至少为O(nK).

注意复杂性O(nK).我认为动态编程可能有所帮助.

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

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

Answer 1

这个问题被观看了36000多次,但我没有看到足够的答案,用逻辑详细解释算法.所以我想我会尝试这样做.

假设:

为了简单起见,我首先假设输入集X只包含正整数并且k是正数.但是,我们可以调整算法来处理负整数,如果k是负数,则可以调整.

逻辑:

这个算法或者任何DP问题的关键在于解决问题并从基本情况开始.然后我们可以使用我们知道的一些知识在基础案例的基础上构建:

1. 我们知道如果集合X是空的,那么我们就无法求和任何值k.
2. 如果一个集合X包含k那么它有一个子集和k.
3. 我们知道,如果集合的子集x1是谁的子集X总和k1,然后X将有一个子集总和k1即x1.
4. 我们有一套X = {x1, x1, x3, ......., xn, xn+1}.我们知道它有一个子集和,k1如果x1 = {x1, x1, x3, ......., xn}有一个子集和k - k1.

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

1. 这很容易.如果你有一个空集{}.你不能有一个子集,因此你不能有任何子集和.

2. 集合X = {4}的子集总和为4,因为4它自身是集合的一部分

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

4. 假设你有一个集合X = {1,3,5,2,19},我们想知道它是否有一个子集总和为20.它确实和一种方法可以知道是否x1 = {1,3,5,2}可以求和(20 - 19)= 1.因为x1的子集总和为1然后当我们向集合x1添加19时,我们可以采用新的数字1 + 19 = 20来创建我们期望的总和20.

动态构建矩阵 酷!现在让我们利用上述四个逻辑并从基础案例开始构建.我们打算建立一个矩阵m.我们定义:

• 矩阵m有i+1行和k + 1列.

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

• m [i] [s]返回true或false来表示这个问题的答案:"使用i数组中的第一项可以找到一个子集求和s吗？" m[i][s]返回trueyes和falseno

(注意维基百科的答案或大多数人构建函数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)rememebr 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).它似乎应该是多项式但它不是!它实际上是伪多项式.在这里阅读它

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

从头到尾很难解释文本上的DP问题.但我希望这可以帮助那些试图理解这个问题的人.

Answer 2

由于看起来你的所有数字都是正数,你可以使用动态编程来解决这个问题:

Start将是一个possible大小为K + 1 的布尔数组,第一个值为true,其余为false.第i个值将表示是否可以实现i的子集和.对于集合中的每个数字n,循环遍历possible数组,如果第i个值为真,则将第i + n值设置为true.

最后,如果第k个值为possible真,那么您可以形成k的子集和.O(NK)时间问题解决了.

维基百科关于子集求和问题的页面详细解释了该算法应用于不保证为正的整数集.

Answer 3

我建议阅读Wiki的算法.该算法存在于此,参见伪多项式时间动态规划解的O(P*n)解,解不是多项式时间,是(p,n)中的多项式,但它不是n + log P(输入大小)中的多项式,因为P可以非常大,如2 ^ n,解P*n =(2 ^ n)*n一般不是多项式时间解,但当p由n的某些多项式函数限定时,则是多项式时间算法.

这个问题是NPC,但是有一个Pseudo polynomial time算法,它属于weakly NP-Complete问题,也有Strongly NP-Complete问题,这意味着,你找不到任何pseudo polynomial time算法,除非P = NP,这个问题不在这个问题范围内,所以不知何故很容易.

我说这个尽可能简单,但它不是强NP完全或弱NP完全问题的确切定义.

详情请参阅Garey和Johnson第4章.

Answer 4

看来我迟到了，这是我的两分钱。我们将创建一个boolean[] solution[n+1][k+1]这样solution[i][j]的true，如果使用第一i项（索引0到i-1）我们可以得到和j从集; 别的false。我们将solution[k][n]最终返回：

我们可以推断出以下几点：

1. 如果 sum 为零，则对于任意数量的元素总是可能的答案（空集）。所以都是真的。
2. 如果集合为空，我们就不能有任何子集，因此无法获得任何 K。所以永远不可能有答案。都是假的。
3. 如果子集 X1（X 的子集没有 X 中的最后一个元素）具有 k 的子集和，那么 X 也有它，即 X1。例如对于 X1={1,3,5} 和 k=8，如果 X1 有一个子集和，那么 X={1,3,5,7} 也有一个子集和
4. 对于 i/p 集合 X = {1,3,5,7,19} 和 k=20，如果 X 想知道 20 的子集和的可能性，那么如果 x1={1,3,5,7}可以有 20-19 的子集和，即 1。它仅适用于 k >= 19 即 X 中的最后一个元素。

基于以上几点，我们可以很容易地编写如下算法。

public class SubSetSum {
    boolean[][] solution; 
    int[] input;
    int k;

    public SubSetSum(int[] input, int targetSum) {
        this.input = input;
        this.k = targetSum;
        this.solution = new boolean[input.length+1][k+1];
    }

    public boolean subsetSum() {
        int n = input.length;

        for (int i = 0; i <= n; i++) {     //case 1
            solution[i][0] = true;
        }

        for (int j = 0; j <= k; j++) {    // case 2
            solution[0][j] = false;
        }

        for (int i = 1; i <= n; i++) {                  // n times
            for (int j = 1; j <= k; j++) {              // k times and time complexity O(n*k)
                if(solution[i-1][j]) {
                    solution[i][j] = solution[i-1][j];      // case 3
                    continue;
                }
                if(j >= input[i-1])  {                       // case 4
                    solution[i][j] = solution[i-1][j-input[i-1]];
                }
            }
        }
        return solution[n][k];
    }
}