Since my TA just quit after giving us this Lab i thought it wouldn't do much harm to ask for a little guidance on here.

The problem is I need to write a 2 dimensional dynamic programming solution to this subset sum problem. The number of ints in the set will be taken in first, followed by the target value. After taking in all the items in the set it will find 3 possible ways in the set to get the target value.

Such as if the target is 10, and the set is 5,5,2,4,6,8... the output would be 5,5...2,8...4,6

If there isnt 3 subsets that sum to the target then it will exit the program, if there is more than 3 it will just print 3 of them.

So far i have written this 1 dimensional subset sum solution.

Could anyone tell me how i would go about making it a 2 dimensional dynamic program, or explain it a little better in detail to me? From the little bit of info i got out of the TA before he quit, i think i need to make array C a 2D array and work from there. Is this a correct approach?

Any guidance would be much appreciatedCode:#include <stdio.h> #include <stdlib.h> main() { // Get input sequence int n; // Size of input set int m; // Target value int *S; // Input set int *C; // Cost table int i,j,potentialSum,leftover; scanf("%d",&n); scanf("%d",&m); S=(int*) malloc((n+1)*sizeof(int)); C=(int*) malloc((m+1)*sizeof(int)); if (!S || !C) { printf("malloc failed %d\n",__LINE__); exit(0); } S[0]=0; // Sentinel zero for (i=1;i<=n;i++) scanf("%d",S+i); // Initialize table for DP C[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]==(-1)) // No way to achieve leftover continue; if (C[leftover]<j) // Indices are included in break; // ascending order. } if (j<=n) { C[potentialSum] = j; } else { C[potentialSum] = (-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(" i C\n"); printf("-------\n"); for (i=0;i<=m;i++) printf("%3d %3d\n",i,C[i]); /**/ if (C[m]==(-1)) printf("No solution\n"); else { printf("Solution\n"); printf(" i S\n"); printf("-------\n"); for (i=m;i>0;i-=S[C[i]]) printf("%3d %3d\n",C[i],S[C[i]]); } }

Thanks