# recursive maximal combination

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 02-22-2011
newyork
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"); }```
• 02-22-2011
itCbitC
Iterate (recursively) until you get the longest sequence that is <= n.
• 02-23-2011
newyork
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]
• 02-23-2011
newyork
i want to know whats the base case
and whats the itterative step

i need to see the logic of it
• 02-23-2011
quzah
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.
• 02-24-2011
newyork
i need to present the combination which will get me as close as i can to N

what are the base cases to use???
• 02-24-2011
newyork
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
?
• 02-24-2011
iMalc
What you're working on is called the Knapsack problem.
Quote:

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
• 02-24-2011
newyork
it doesnt say there what base case to use
• 02-24-2011
nonoob
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.
• 02-24-2011
newyork
but i want maximal sum as close as possible to N

(<=N)
it differs then just =N which you proposed
• 02-24-2011
nonoob
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.
• 02-24-2011
newyork
i cant "iterate through the array" because its not an itterative problem ,it a recursive problem

what base case should i use?
• 02-24-2011
quzah
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.
• 02-24-2011
newyork
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?
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last