// Subset sums by dynamic programming // CSE 2320 Notes 7 #include #include void readInput(int* n,int* m,int** S,int** C) { // Loads all input and allocates space int i; 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); } void subsetSum(int n,int m,int* S,int* C) { int i,j,potentialSum,leftover; // 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 && // Possible to have a solution C[leftover]0;i-=S[C[i]]) printf("%3d %3d\n",C[i],S[C[i]]); } } int main() { int n; // Size of input set int m; // Target value int *S; // Input set int *C; // Cost table readInput(&n,&m,&S,&C); subsetSum(n,m,S,C); writeOutput(n,m,S,C); free(S); free(C); }