c - 如何在 C 中找到子集总和(使用动态规划)中的所有子集

Question

我是 C 的新手(学习了 1.5 个月)，我们的大学教授要求我们找到子集和问题的动态规划解决方案(以及其他 2 个问题)，但我已经按照他的指示进行操作，并且我'我坚持如何实际找到(打印)请求的子集。有人可以帮助我了解它的工作原理以及如何找到所有子集吗？

对于下面的代码，表格是{3,2,1,2,4,3,4,1}，子集需要加起来为7。

编辑! --> 我修改了初始代码，以便找到总和为特定值的子集数量(在我们的例子中为 7，子集为 20)。我重复一遍，我需要帮助来找到总和为一个值(在本例中为 7)的所有子集(组合)。

在上面的例子中，这意味着代码能够打印 20 个子集，它们是:

子集 1:3 2 1 1
子集 2: 3 2 2
子集 3: 3 1 2 1
子集 4: 3 1 3
子集 5: 3 4
子集 6: 3 3 1
子集 7: 3 4
子集 8: 2 1 4
子集 9: 2 1 3 1
子集 10: 2 1 4
子集 11: 2 2 3
子集 12: 2 4 1
子集 13: 2 4 1
子集 14: 1 2 4
子集 15: 1 2 3 1
子集 16: 1 2 4
子集 17: 2 4 1
子集 18: 2 4 1
子集 19: 4 3
子集 20: 3 4

在接下来的 C 代码中，我能够打印指令要求我打印的表格，并且通过该表格我必须找到所有子集。该表的说明是:

x[i][j]=x[i-1][j];
如果(j>=y[i-1]) x[i][j]+=x[i-1][j-y[i-1]];

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
long set[] = {3,2,1,2,4,3,4,1};
long sum =7;
long n = sizeof(set)/sizeof(set[0]);
iter_subset_sum(set, n, sum);
return 0;
}

int iter_subset_sum (int *y, long n, long sum) {
  int i,j,k,**x;
  x=malloc((n+1)*sizeof(long**));
  for(i=0;i<=n;i++)
    x[i]=malloc((sum+1)*sizeof(long*));

  for (i=0; i<=n; i++)
    x[i][0] = 1;    
  for (i=1; i<=sum; i++)
    x[0][i] =0;
  for (i=1; i<=n; i++) {    
    for (j=1; j<=sum; j++){
    x[i][j]=x[i-1][j];
    if(j>=y[i-1])
        x[i][j]+=x[i-1][j-y[i-1]];  }   }
  for (i = 0; i <= n; i++){
        for (j = 0; j <= sum; j++)
          printf ("%4d", x[i][j]);
              printf("\n");
      }
      printf("There are %d subsets :", x[n][sum]);
}

非常感谢您!如果你能帮助像我这样想慢慢“深入”C语言的新手，我将不胜感激......

Answer 1

#include <stdio.h>
int iscan(int a[],int n,int sum){
    int f[sum+1],m=0,i,j,k,el,o=0;
    for(i=1;i<=sum;i++)f[i]=0;f[0]=1;
    for(i=0;i<n;i++){
        el=a[i];
        if(el>sum)continue;
        m=m+el>sum?sum:m+el;
        for(k=m-el,j=m;k>=0;j--,k--){
            if(f[k]){
                /* f[j]=el;*/ //old only last conest
                            push_toarray_of_stack(on j position ,item size of el);;//this pseudocode is hint for u homework*********** so and change printing all combination after builing array_of_stack's  of conection

            }
        }
        if(!f[sum])continue;
        k=sum;
        while(k){
            printf("%d ",f[k]);
            k-=f[k];
        }
        printf("%s\n","");
        //exit(0); 
            o++;
    }
    //printf("%s\n","can't");
    return o;
}

int main(){
  int set[] = {1, 3, 2, 4, 2, 6, 5};
  int sum = 5;
  return iscan(set,sizeof(set)/sizeof(set[0]),sum);
}