c/c++ code

[anaychowdhary]

hi, I am looking for the code for the following program. Consider a set of elements and a given sum. You need to find a subset of elements whose sum equals or is greater[given there are more than one subset, print the one whose sum is closest to the number] to that number.
PS: it's similar to subset sum problem.
thanks

[Narue]

We don't give away code so that students can cheat on their homework. If you want to put forth some effort in writing this program you'll find help here, otherwise the thread will be in violation of Daniweb's rules and be either closed or deleted.

[anaychowdhary]

the code i have written calculates for the sum to be equal to the given number. I have tried to test run and see, what modifications i could make to satisfy the problem statement, could not come across a solution. Also i am an electrical engineering student, i do not have much idea of c/c++.

[Narue]

the code i have written

Doesn't exist in our perspective until you post it. Show us what you have, tell us what you've tried, and someone will help you move forward.

[anaychowdhary]

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

I cannot figure out the changes required that will satisfy the problem statement.
My friend helped me out in writing the above code. I am using it for calculating the required load to be shed for power transmission.
-Anay

[anaychowdhary]

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

I cannot figure out the changes required that will satisfy the problem statement.
My friend helped me out in writing the above code. I am using it for calculating the required load to be shed for power transmission.
-Anay

[NathanOliver]

there is a simple approach to this problem. start at the begining of the array and sum all of the elements untill you reach your goal. then you need to store the begining and end posistion of that subset. then you will start at the 2nd element of the array and do the same process. if your result is better than overwrite the posistions and the total. keep doing this untill you run to the end of the array and your total is still not greater than the number you are looking for

[anaychowdhary]

the approach you mentioned will not get the best subset possible.
consider there are five number 8,11,14,17,80 and the given sum is 89
the output by the approach you mentioned will be 97[17,80] whereas is should be 91[11,80]. So i need to look for the best subset possible.

[NathanOliver]

So your sub set does not need to be continuous then?

[arkoenig]

This looks like a version of the NP-complete knapsack problem to me.

[anaychowdhary]

@ NathanOliver yes, the subset does not need to be continuous.
@ arkoenig it is very similar to subset problem, just the condition that the sum can be greater than the given number as well.