如何使用 C 中的动态编程查找总和等于目标值的所有子集

Question

所以我一直在尝试做一个子集和问题的变体，我想用动态规划来做。所以我的目标是例如输入

m = 25 // Target value

n = 7 // Size of input set

并且输入设置为例如 {1, 3, 4, 6, 7, 10, 25}。所以想要的输出类似于

{1, 3, 4, 7, 10} and {25}.

这是代码

#include <stdio.h>
#include <stdlib.h>

int main()
{
    // Get input sequence
    int n = 7;    // Size of input set
    int m = 25;    // Target value
    int *S;   // Input set
    int **C;   // Cost table
    int i,j,potentialSum,leftover;
    S=(int*) malloc((n+1)*sizeof(int));
    C=malloc((m+1)*sizeof(int*));
    for (int rows = 0; rows<=m; rows++) {
        C[rows] = malloc((m+1)*sizeof(int));
    }
    if (!S || !C)
    {
        printf(" FAILED %d\n",__LINE__);
        exit(0);
    }
    S[0] = 0;
    S[1] = 1;
    S[2] = 3;
    S[3] = 4;
    S[4] = 6;
    S[5] = 7;
    S[6] = 10;
    S[7] = 25;

    // Initialize table for DP
    C[0][0]=0;  // DP base case

    // For each potential sum, determine the smallest index such
    // that its input value is in a subset to achieve that sum.
    for (potentialSum=1; potentialSum<=m; potentialSum ++)
    {
        for (j=1;j<=n;j++)
        {
            leftover=potentialSum-S[j];      // To be achieved with other values
            if (leftover<0)                  // Too much thrown away
                continue;
            if (C[leftover][0] == (-1))           // No way to achieve leftover
                continue;
            if (C[leftover][0]<j)               // Indices are included in
                break;                         // ascending order.
        }
        C[potentialSum][0]=(j<=n) ? j : (-1);
    }

    // Output the input set
    printf("  i   S\n");
    printf("-------\n");
    for (i=0;i<=n;i++)
        printf("%3d %3d\n",i,S[i]);

    // Output the DP table
    printf("\n\n  i   C\n");
    printf("-------\n");
    for (i=0;i<=m;i++)
        printf("%3d %3d\n",i,C[i][0]);

    if (C[m][m]==(-1))
        printf("No solution\n");
    else
    {
        printf("\n\nSolution\n\n");
        printf("(Position) i   S\n");
        printf("------------------\n");
        for (i=m;i>0;i-=S[C[i][0]])
            printf("        %3d %3d\n",C[i][0],S[C[i][0]]);
    }
}

这将输出以下内容

 i   S
-------
  0   0
  1   1
  2   3
  3   4
  4   6
  5   7
  6  10
  7  25

  i   C
-------
  0   0
  1   1
  2  -1
  3   2
  4   2
  5   3
  6   4
  7   3
  8   3
  9   4
 10   4
 11   4
 12   5
 13   4
 14   4
 15   5
 16   5
 17   5
 18   5
 19   6
 20   5
 21   5
 22   6
 23   6
 24   6
 25   6

Solution

(Position) i   S
------------------
          6  10
          5   7
          3   4
          2   3
          1   1
Program ended with exit code: 0

我的问题是我只能输出一个解决方案，那就是需要较小值并达到 25 的解决方案，所以当使用 25 时，它不在解决方案中。代码中的 C 数组是一个二维数组，因为我认为我可以在计算第一个时做另一个回溯？我不知道该怎么做，所以我将 C[i][0] 固定在第一列，只是为了演示一个解决方案。任何正确方向的提示将不胜感激。我找到了使用 Python 的解决方案，但问题是递归解决的，我认为这对我没有帮助，但该代码是 here.

提前感谢大家的帮助。

Answer 1

我没有完全理解你的代码。但是这里有一个 C 代码，它找到总和为 target.

的所有子集

#include <stdio.h>

int a[] = { 0, 1, 3, 4, 6, 7, 10, 25 };     //-- notice that the input array is zero indexed
int n = 7;
int target = 25;
int dp[8][26];

int solutions[1 << 7][8];           //-- notice that the number of subsets could be exponential in the length of the input array a.
int sz[1 << 7];                     //-- sz[i] is the length of subset solutions[i]
int cnt = 0;                        //-- number of subsets




void copy(int srcIdx, int dstIdx){
    int i;
    for (i = 0; i < sz[srcIdx]; i++)
        solutions[dstIdx][i] = solutions[srcIdx][i];
    sz[dstIdx] = sz[srcIdx];
}

//-- i, and j are indices of dp array
//-- idx is the index of the current subset in the solution array
void buildSolutions(int i, int j, int idx){
    if (i == 0 || j == 0) return;           // no more elements to add to the current subset

    if (dp[i - 1][j] && dp[i - 1][j - a[i]]){   // we have two branches
        cnt++;                                  // increase the number of total subsets
        copy(idx, cnt);                         // copy the current subset to the new subset. The new subset does not include a[i]
        buildSolutions(i - 1, j, cnt);          //find the remaining elements of the new subset 

        solutions[idx][sz[idx]] = a[i];         // include a[i] in the current subset
        sz[idx]++;                              // increase the size of the current subset
        buildSolutions(i - 1, j - a[i], idx);   // calculate the remaining of the current subset
    }
    else if (dp[i - 1][j - a[i]]){              // we only have one branch
        solutions[idx][sz[idx]] = a[i];         // add a[i] to the current subset     
        sz[idx]++;
        buildSolutions(i - 1, j - a[i], idx);     // calculate the remaining of the current subset
    }
    else buildSolutions(i - 1, j, idx);           // a[i] is not part of the current subset

}

int main(){

    int i, j;

    // initialize dp array to 0
    for (i = 0; i <= n; i++)
        for (j = 0; j <= target; j++) dp[i][j] = 0;

    //-- filling the  dp array
    for (i = 0; i <= n; i++)
        dp[i][0] = 1;
    for (i = 1; i <= n; i++){
        for (j = 1; j <= target; j++){
            if (j < a[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - a[i]];
        }
    }

    //-- building all the solutions
    for (i = 0; i < sizeof(sz); i++) sz[i] = 0;     //-- initializing the sz array to 0
    buildSolutions(n, target, 0);


    //-- printing all the subsets
    for (i = 0; i <= cnt; i++){
        for (j = 0; j < sz[i]; j++){
            printf("%d ", solutions[i][j]);
        }
        printf("\n");
    }

}

如果您对代码有任何疑问，请随时提问。

如何使用 C 中的动态编程查找总和等于目标值的所有子集

How to find all subsets whose sum adds up to the value of a target value using dynamic programming in C

c

dynamic-programming

backtracking

subset-sum