Subset Sum (동적 프로그래밍 포함)의 모든 하위 집합을 찾는 방법

Question

저는 C (1.5 개월 공부 중)에서 새로 왔으며 우리 대학 교수는 Subset Sum 문제의 동적 프로그래밍 솔루션을 찾을 것을 요청했습니다. 2 다른 것들),하지만 난 그의 지시를 따르고 요청 된 하위 집합을 실제로 (인쇄)하는 방법에 붙어있다. 누군가가 어떻게 작동하는지 이해하고 하위 집합을 모두 찾는 법을 배울 수 있습니까? 아래의 코드를

이 테이블은 {3,2,1,2,4,3,4,1}, 그리고 집합은 7

EDIT로 요약 할 필요가! -> 초기 코드를 수정하여 특정 값까지 합계 한 부분 집합의 수를 확인했습니다 (이 경우 7이고 하위 집합은 20 개입니다). 나는 값 (이 경우 7)까지 합한 모든 하위 집합 (조합)을 찾는 데 도움이 필요하다는 것을 반복합니다.

서브셋 1 : 3 2 1 1
부분 2 : 3 2 2
부분 3 : 3 위의 경우

,이 코드는 20 개 개의 서브 세트를 인쇄 할 수있는 것을 의미 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
012 3,516,부분 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 : I는 수있어 이하의 C 코드 3 4

테이블을 인쇄하려면 지시는 나를 원해.이 표를 통해 나는 모든 하위 집합을 찾아야 만한다. 테이블에 대한 지침은 있었다 :

x[i][j]=x[i-1][j]; if(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); 
}