Thread: recursive maximal combination

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    53

    recursive maximal combination

    i got a bag which can take "n" kilograms inside of him
    and i have a list of items in which each item has a different weight.

    i need to calculate a combination for which it will fill the bag as much as it could
    without passing the n kilograms mark.

    i got a function which calculates if amongnt the array we have a combination
    which sum equals n (S=n)

    how to change it so it will calculate a combination for which it will fill the bag as much as it could
    without passing the n kilograms mark. S<=n

    ??
    Code:
    #include <stdio.h>
    
    void printArr(int arr[], int n)
    {
    	int i ;
    	puts("");
    	for (i=0; i<n; i++)
    		printf (" %d",arr[i]);
    	puts("");
    }
    
    int SubsetSum(int arr[], int n, int S, int subseq[],int count)
    {
    	int withCurrent, withoutCurrent;
    	if (S==0) 
    	{
    		printArr(subseq,count);
    		return 1;
    	}
    	if (S< 0 || !n) 
    		return 0;
    	subseq[count] = arr[0];
    	withCurrent = SubsetSum(arr+1,n-1,S-arr[0],subseq, count+1);
    	withoutCurrent= SubsetSum(arr+1,n-1,S,subseq,count);
    	return (withoutCurrent || withCurrent);
    }
    
    void main()
    {
    	int arr[] = {7, 6, 5,1,7,13,17}, subseq[8];
    	int S = 14,arrSize = 7;
    
    	if (!SubsetSum(arr,arrSize,S,subseq,0))
    		printf("\nThere is no subsequence\n");
    }
    Last edited by newyork; 02-22-2011 at 03:19 PM.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Iterate (recursively) until you get the longest sequence that is <= n.

  3. #3
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    i need to use here a string to strore to final sequence

    how recursivly go by every combination of the array

    Code:
    int max(int arr[],n)
    {
    
    
      max(arr+1,n);
    }
    why we need iterative step here
    we dont need the resolt of n-1 problem here

    ??

    [/code]

  4. #4
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    i want to know whats the base case
    and whats the itterative step

    i need to see the logic of it

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What are you actually trying to calculate? Are you just trying to get as close to N as you can, or are you trying to get as close to N as you can AND use as many elments in your array as you can?

    If the latter, then you need to be keeping track of how many you have used.

    Or are you trying to generate the list of all the ones you are using? Because that's going to take some more doing. You will either need to keep track of the index of everyone used, or the value, in an array some place.

    Let's assume you just want to get as close to N as possible:
    Code:
    while X < N && C < ARRAY LEN
        if array[ c ] <= N - X
            N += array[ c ]
        C++
    The only difference between the two versions I mentioned first, is that you increase a counter of how many different elements you have been using also, and that's what the function returns. Since it's recursive if any calls you have made returned anything more than 0, it means they used something further along than where you are currently, so return 1 (for where you are) plus the value they returned.

    At least that's probably how I'd do it. Of course I'd probably use more than 2 arguments again.


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    i need to present the combination which will get me as close as i can to N

    what are the base cases to use???

  7. #7
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    i need to know the basic logic of the solution
    recursive thinking differs itterative

    i can think of a base case where i have a array of 1 cell
    what should i do with it
    ?

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    What you're working on is called the Knapsack problem.
    the problem is NP-complete to solve exactly, thus it is expected that no algorithm can be both correct and fast (polynomial-time) on all cases
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    it doesnt say there what base case to use

  10. #10
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Interesting problem. You have to iterate through the array for 1 number... so see which case equals the desired weight.
    Failing that, find all combinations of 2 entries whose sum equals the desired weight.
    Failing that, find all combinations of 3 entries...
    It is tricky to set up a dynamic nested loop construct to do a N-many-elements nested loops.

    Another approach I just thought of would be to simply make a counter that goes from 0 to 2^arrSize -1.

    For example, arrSize is 7. So a counter should go from 0 to 127.
    For each value, look at the binary representation of the counter. Because the bits will go through every combination, they could represent the selection of elements. This method would force you to become familiar with bit masking, shifting, etc.

    Every '1' bit in the integer would indicate select the corresponding element from arr[]. A 0 means do not select. Sum up the selected elements. If you find a combination that equals the desired total you can stop.

  11. #11
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    but i want maximal sum as close as possible to N

    (<=N)
    it differs then just =N which you proposed

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Same algorithm would be employed. You'd have to keep track of which combination got closest to N by keeping track of the least difference so far.

  13. #13
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    i cant "iterate through the array" because its not an itterative problem ,it a recursive problem

    what base case should i use?

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why don't you just sort the array from low to high, and take the first part of the array until you reach or exceed N? If all you care about is getting the longest chain possible, that would be your best bet.


    Quzah.
    Hope is the first step on the road to disappointment.

  15. #15
    Registered User
    Join Date
    Feb 2011
    Posts
    53
    the problem doesnt allow me to change the array
    and i cant "iterate through the array" because its not an itterative problem ,it a recursive problem

    what base case should i use?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  2. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  3. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM