Thread: Subset Sums and 2D Dynamic Programming

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?

Code:

#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]]);
}
}

Any guidance would be much appreciated

Thanks

I'm sure you'll want a 2D dynamic array, if you have an exercise that requires them. Is the idea that you will be searching for sums leading out from every element of the 2D array, on columns as well as rows? What about diagonals from every element, do you need to search for matches there, also?

Ok, ive done some planning and id like to know if you think this would be a good solution.

What if i ran this program as is but without a print. Once done remove the items that are a solution from the set array S. Then i run it again but place the C array operations in a 2nd dimension... i do this 3 times total, and when i print i print over a 2D C array instead of a 1D.

Hope that makes sense..

You think it would work? and is that classified as 2D dynamic programming?

The position (rows and column number) of the set of values to be searched through, should be an intrinsic part of the program. You can't solve the problem, without using the properties of the 2D array.

I'm wondering if it's to be like a game of scrabble, except you're to look for a target value, among numbers, instead of words among letters?

A brute force search would be substantially different than your previous post above. More set up around the properties of the 2D array:

Code:

for(each row) { 
   for (each column) {
      while (sum < target value && column < MAX_COL) {
         add a sum of values along this row

         if a target value is found, record the row and column of the  
         start and finish positions
      }      
      now you have three other vectors to check with their own while
      loops.
   }
}

Having heard not one word out of the lecture or TA's description, I have no idea if this is the problem they meant for you to solve, however.

dude... just try to figure out something from the output data he has given. I think that really does help!