子集和算法

Question

我正在研究这个问题：

子集和问题将一组 X = {x1, x2 ,…, xn}（由 n 个整数组成）和另一个整数 K 作为输入>。问题是检查 X 是否存在其元素总和为 K 的子集 X'，并查找该子集（如果有）。例如，如果 X = {5, 3, 11, 8, 2} 且 K = 16 则答案为 YES，因为子集X' = {5, 11} 的总和为 16。实现一个子集和算法，其运行时间至少为 O(nK)。

注意复杂度O(nK)。我认为动态规划可能会有所帮助。

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

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

Answer 1

看来我参加聚会迟到了，这是我的两分钱。我们将创建一个 boolean[] Solution[n+1][k+1]，使得 solution[i][j] 为 true如果使用前 i 项（索引 0 到 i-1），我们可以从集合中得到总和 j；否则假。我们最终将返回solution[k][n]：

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

1. 如果sum为零，则对于任意数量的元素总是一个可能的答案（空集）。所以一切都是真的。
2. 如果 set 为空，我们就不能有任何子集，因此无法获得任何 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];
    }
}

Answer 2

在一般情况下，没有已知的子集和算法运行时间小于 O(2^(n/2))。

Answer 3

void subsetSum (int arr[], int size, int target) {
  int i, j ;
  int **table ;
  table = (int **) malloc (sizeof(int*) * (size+1)) ;
  for ( i = 0 ; i <= size ; i ++ ) {
    table[i] = (int *) malloc (sizeof(int) * (target+1)) ;
    table[i][0] = 1 ;
  }
  for ( j = 1 ; j <= target ; j ++ )
    table[0][j] = 0 ;
  for ( i = 1 ; i <= size ; i ++ ) {
    for ( j = 1 ; j <= target ; j ++ )
      table[i][j] = table[i-1][j] || (arr[i-1] <= j && table[i-1][j-arr[i-1]] ) ;
  } 
  if ( table[size][target] == 1 )
    printf ( "\ntarget sum found\n" ) ; 
  else printf ( "\nTarget sum do not found!\n" ) ;
  free (table) ;
}

Answer 4

设 M 为所有元素的总和。
注意 K<=M

let m be a Boolean array [0...M]
set all elements of m to be False
m[0]=1
for all numbers in the set let a[i] be the ith number
    for j = M to a[i]
        m[j] = m[j] | m[j-a[i]];

然后简单测试 m[k]

Answer 5

boolean hasSubset(int arr[],int remSum,int lastElem){
    if(remSum==0) return true;
    else if(remSum!=0 && lastElem<0) return false;

    if(arr[lastElem]>remSum) return hasSubset(arr, remSum, lastElem-1);
    else return (hasSubset(arr, remSum, lastElem-1) ||hasSubset(arr, remSum-arr[lastElem], lastElem-1));
}

考虑第 i 个元素。它要么会对子集总和做出贡献，要么不会。如果它对总和有贡献，则“总和的值”会减少等于第 i 个元素的值。如果它没有贡献，那么我们需要在剩余元素中搜索“和的值”。

Answer 6

上面的答案都很好，但并没有真正给出像这样的东西如何适用于正数和负数的最广泛概述。

给定一个有序的整数集，定义两个变量 X 和 Y，使得

X = 负元素之和

Y = 正元素之和

，并按此顺序应用这些规则来对初始集进行操作，就像在二叉树中递归一样

1. 如果最右边的元素等于您要检查的总和
   for return true
2. 递归 left 如果这样做不会留下空
   set，从排序数组中删除最右边的元素
3. 如果集合中还剩下一个元素，并且它不是总和，则返回 false 而不是
4. 递归右侧，而是检查集合中所有元素的总和
   数组 q，如果 X <= B <= Y 则返回 true，如果不返回 false
5. 如果左子树或右“递归”返回 true，则向父级返回 true

上面的答案更详细和准确，但对于非常广泛地了解这应该如何发挥作用，绘制一棵二叉树。这个长度对运行时间有何影响？

Answer 7

function subsetsum(a, n) {
    var r = [];
    for (var i = parseInt(a.map(function() { return 1 }).join(''), 2); i; i--) {
        var b = i.toString(2).split('').reverse().map(function(v, i) {
            return Number(v) * a[i]
        }).filter(Boolean);
        if (eval(b.join('+')) == n) r.push(b);
    }
    return r;
}

var a = [5, 3, 11, 8, 2];
var n = 16;
console.log(subsetsum(a, n)); // -> [[3, 11, 2], [5, 3, 8], [5, 11]]

蛮力——忘记排序，尝试每一个组合，eval 解析器击败 Array.reduce（它也适用于负数）。

Answer 8

时间复杂度为 n^2 的递归解决方案

public void solveSubsetSum(){
    int set[] = {2,6,6,4,5};
            int sum = 9;
            int n = set.length;

            // check for each element if it is a part of subset whose sum is equal to given sum
            for (int i=0; i<n;i++){
                if (isSubsetSum(set, sum, i, n)){
                    Log.d("isSubset:", "true") ;
                    break;
                }
                else{
                    Log.d("isSubset:", "false") ;
                }
                k=0; // to print time complexity pattern
            }
        }

private boolean isSubsetSum(int[] set, int sum, int i, int n) {

            for (int l=0;l<k; l++){
            System.out.print("*"); 
            // to print no of time is subset call for each element
        }
        k++;
        System.out.println();     
        if (sum == 0){
            return true;
        }

        if (i>=n){
            return false;
        }

        if (set[i] <= sum){ 
        // current element is less than required sum then we have to check if rest of the elements make a subset such that its sum is equal to the left sum(sum-current element)
            return isSubsetSum(set, sum-set[i], ++i, n);
        }
        else { //if current element is greater than required sum
            return isSubsetSum(set, sum, ++i, n);
        }
   }

最坏情况复杂度： O(n^2)

最好情况： O(n) 即；如果第一个元素构成一个子集，其总和等于给定的总和。

如果我在这里计算时间复杂度是错误的，请纠正我。

Answer 9

一维数组的 DP 解决方案（DP 数组处理顺序在这里很重要）。

bool subsetsum_dp(vector<int>& v, int sum)
{
    int n = v.size();
    const int MAX_ELEMENT = 100;
    const int MAX_ELEMENT_VALUE = 1000;
    static int dp[MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for (int i = 0; i < n; i++)
    {
        for (int j = MAX_ELEMENT*MAX_ELEMENT_VALUE; j >= 0; j--)
        {
            if (j - v[i] < 0) continue;
            if (dp[j - v[i]]) dp[j] = 1; 
        }
    }

    return dp[sum] ? true : false;
}

Answer 10

Subset Sum 是我在 Macalester 学到的第一个 NP 完全问题。这个问题被浏览了 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}。如果 x1 = {x1, x1, x3, ......., xn} 的子集和为 k1，我们知道它的子集和为 k1 >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然后当我们将 19 添加到集合 x1 中时
   我们可以用新的数字 1 + 19 = 20 来创建我们想要的总和 20。

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

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

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

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

（请注意维基百科的答案或大多数人构建一个函数 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)。看起来它应该是多项式，但事实并非如此！它实际上是伪多项式。请在此处阅读相关内容。

同样，这只在输入仅包含正数时才有效。您可以轻松调整它以处理负数。该矩阵仍将有 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)));

Answer 11

由于看起来所有数字都是正数，因此您可以使用动态编程来解决此问题：

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

最后，如果possible中的第k个值为true，那么就可以形成k的子集和。问题在 O(NK) 时间内解决。

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

Answer 12

我建议阅读 Wiki 的算法。该算法存在于其中，O(P*n) 解参见伪多项式时间动态规划解，该解不是多项式时间，是 (p, n) 但它不是 n+log P（输入大小）中的多项式，并且因为 P 可能非常大，如 2^n，所以解 P*n = (2^n)*n 不是一般而言，多项式时间解是多项式时间算法，但当 p 受 n 的某个多项式函数限制时，则为多项式时间算法。

这个问题是NPC，但有一个伪多项式时间算法，属于弱 NP 完全性问题，还有 强NP完全问题，这意味着，除非P=NP，否则你找不到任何伪多项式时间算法，并且这个问题不存在这一系列的问题，所以不知何故很容易。

我说得尽可能简单，但这并不是强 NP 完全问题或弱 NP 完全问题的精确定义。

有关详细信息，请参阅Garey 和 Johnson 第 4 章。