Subset Sums and 2D Dynamic Programming

This is a discussion on Subset Sums and 2D Dynamic Programming within the C Programming forums, part of the General Programming Boards category; Since my TA just quit after giving us this Lab i thought it wouldn't do much harm to ask for ...

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    14

    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

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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?

  3. #3
    Registered User
    Join Date
    Sep 2010
    Posts
    14
    I believe its just columns as wells as rows, here is a sample output of what the code should do when finished. I'll be honest, i'm really confused on this Lab but it seems most of the class is in the same boat. We have yet to get a new TA, so we are all pretty much thrown into this face first. Any help explaining it would be great.


    Code:
     Target value is 9
     Set = {1,2,3,4,4,5,8}
    Code:
    Output:
      i    0    1    2
      1    1
      2              2
      3              3
      4              4
      5         4
      6         5
      7    8
    Last edited by Trooper88; 11-11-2011 at 03:32 PM.

  4. #4
    Registered User
    Join Date
    Sep 2010
    Posts
    14
    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?

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    1
    dude... just try to figure out something from the output data he has given. I think that really does help!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. subset algorithm
    By calc in forum C Programming
    Replies: 5
    Last Post: 06-24-2009, 01:06 PM
  2. Subset
    By oxair in forum C++ Programming
    Replies: 4
    Last Post: 09-28-2006, 04:54 AM
  3. Subset problem
    By Spectrum_tr in forum C Programming
    Replies: 3
    Last Post: 12-05-2005, 03:35 PM
  4. Find all possible subset of a given set
    By Downnin in forum C++ Programming
    Replies: 7
    Last Post: 11-09-2005, 02:03 PM

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