子集求和算法 [英] Subset Sum algorithm

问题描述

我正在解决这个问题:

子集和问题将 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).

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).我认为动态规划可能会有所帮助.

Notice complexity O(nK). I think dynamic programming may help.

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

I have found an exponential time algorithm, but it doesn't help.

有人能帮我解决这个问题吗?

Can someone help me solve this problem?

推荐答案

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

Subset Sum is the first NP-complete problem I learned at Macalester. This question is viewed 36000+ times yet I don't see a sufficient answer that explains the algorithm in detail with logic. So I thought I make an attempt to do so.

假设:

为了简单起见，我首先假设输入集 X 只包含正整数，而 k 是正整数.但是，我们可以调整算法来处理负整数和 k 为负的情况.

For the sake of simplicity first I made the assumption that the input set X contains only positive integers and k is positive. However, we can tweak the algorithm to handle negative integers and the case if k is negative.

逻辑:

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

The key to this algorithm or really any DP problem is to break down the problem and start simply from a base case. then we can build on the base case using some knowledge that we know:

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

1. we know that if the set X is empty then there is no way we can sum to any value of k.
2. If a set X contains k then it has a subset sum to k.
3. we know that if a subset of set x1 who is a subset of X sum to k1 then X will have a subset that sum to k1 namely x1.
4. we have a set X = {x1, x1, x3, ......., xn, xn+1}. We know it has a subset sum to k1 if x1 = {x1, x1, x3, ......., xn} has a subset sum to k - k1.

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

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

2. 集合 X = {4} 的子集和为 4，因为 4 它本身就是集合的一部分

1. it is easy. if you have an empty set {}. you can't have a subset thus you can't have any subset sum.

2. A set X = {4} has a subset sum to 4 because 4 it self is part of the set

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

say you have a set x1 = {1,3,5} who is a subset of set X = {1,3,5,2,8}. if x1 has a subset sum to k1 = 8 then that means X also has a subset sum to 8 because x1 is a subset of X

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

Dynamically build a matrix Cool! now let us utilize the above four logics and start building from the base case. We are going to build a matrix m. We define:

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

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

Each cell of the matrix has value true or false.

m[i][s] 返回 true 或 false 来指示这个问题的答案:使用数组中的第一个 i 项，我们可以找到 的子集和>s? " m[i][s]返回 true 表示是，false 表示否

m[i][s] returns true or false to indicate the answer to this question: "using the first i items in the array can we find a subset sum to s? " m[i][s]returns true for yes and false for no

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

(note the Wikipedia answer or most of the people build a function m(i,s) but I thought the matrix is an easy way to understand dynamic programming. It works well when we only have positive numbers in the set or array. However the function route is better because you don't have to deal with index out of range, match index of the array and sum to the matrix.....)

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

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

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

We are going to build the matrix row by row. We ultimately want to know the cell m[n][k] contain true or 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 来帮助我们填充矩阵.

Second Row and above: Then for the second row or above, we can use logic 2,3,4 to help us populate the matrix.

• 逻辑 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] 个细胞.

• logic 2 tells us that m[i][s] = (X[i-1] == s) rememebr m[i] is referring to the ith item in X which is X[i-1]
• logic 3 tells us that m[i][s] = (m[i-1][s]) this is looking at the cell direclty above.
• logic 4 tells us that m[i][s] = (m[i-1][s - X[i-1]]) this is looking at the row above and left of X[i-1] cells.

如果其中任何一个是 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]])

If any of these is true then m[i][s] is true otherwise false. so we can rewrite 2,3,4 into m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])

使用上述这些逻辑来填充矩阵 m.在我们的示例中，它看起来像这样.

Use these above logics to populate the matrix m. In our example, it looks like this.

   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

look at m[5][9] which is the original question. using the first 5 items (which is all the items) can we find a subset sum to 9 (k)? and the answer is indicated by that cell which is 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("
");
        }
    }

    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).看起来它应该是多项式的，但它不是！它实际上是伪多项式.在此处

To build the matrix m takes O((n+1)(k+1)) which is O(nk). it seems like it should be polynomial but it is not! It's actually pseudo polynomial. Read about it here

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

Again this only works if the input only contains positive numbers. You can easily tweak it to work with negative numbers tho. The matrix would still have n+1 rows but B - A + 1 columns. Where B is the upperbound and A is the lowerbound ( +1 to include zero).The matrix would still be You would have to offset s with the lowerbound.

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

It is pretty hard to explain DP problem over text from start to end. But I hope this helps those out there that try to understand this problem.

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

Note that in the examples above the rows of the DP table are sorted. That does not have to be the case.

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

Here is a DP table for the case of the question, i.e. given a set of {5, 3, 11, 8, 2}. For brevity, I have omitted the false values.

┌─────────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ (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}:

Below is an implementation in JavaScript which will output the target set {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)));

这篇关于子集求和算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！