Thread: subset sum problem

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    1

    subset sum problem

    Hi..I'm an electrical engineering student.I am building up a program for optimal load prediction and shedding.
    If there are 5 nos.supposing [ 2,8,12,15,20] i want the best combination which is either equal to or greater than a required sum x=36.If no combination is found equal to x=36 then the closest combination which is greater than 36 is used (in this case which is 37 [20,15,2]). I have the following code which uses recursion to find which combination is equal to the required sum but if nothing is found equal it will give no solution and won't check for the closest greater combination.
    Can this code be altered to check for next greater combination if nothing equal is found.If not what other techniques could be used.

    Code:
    #include<stdio.h>
     
    int count,w[10],d,x[10];
     
    void subset(int cs,int k,int r)
    {
       int i;
       x[k]=1;
       if((cs+w[k])>d)
        {
           printf("\n Subset solution = %d\n",++count);
           for(i=0; i<=k; i++)
           {
             if(x[i]==1)
             printf("%d\n",w[i]);
           }
         }
      else if(cs+w[k]+w[k+1] <=d)
            subset(cs+w[k],k+1,r-w[k]);
        if((cs+r-w[k]>=d)&&(cs+w[k+1])<=d)
        {               
          x[k]=0;
          subset(cs,k+1,r-w[k]);
        }
    }
     
    int main()
    {
        int sum=0,i,n;
        printf("enter no of elements\n");
        scanf("%d",&n);
        printf("Enter the elements in ascending order\n");
        for(i=0; i<n; i++)
        scanf("%d",&w[i]);
        printf("Enter the required sum\n");
        scanf("%d",&d);
        for(i=0; i<n; i++)
        sum +=w[i];
     if(sum < d)
        {
            printf("no solution exits\n");
             
        }   
        printf("The solution is\n");
        count =0;
        subset(0,0,sum);
        return 0;
        getch();
    }
    Last edited by archit_mahajan; 05-18-2011 at 02:30 AM.

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, 12:06 PM
  2. Subset
    By oxair in forum C++ Programming
    Replies: 4
    Last Post: 09-28-2006, 03: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