programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Knute Snortum
• Paul Clapham
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• Jeanne Boyarsky
• Bear Bibeault
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Ron McLeod
• Piet Souris
• Frits Walraven
Bartenders:
• Ganesh Patekar
• Tim Holloway
• salvin francis

# Recursion

Ranch Hand
Posts: 50
I am trying to determine the best number of cargo to be fitted onto the ship using recursion. I am clueless on how to proceed hence i need some help in getting ideas to solve.

For this particular problem using recursion, is it right that i use if total weight exceeds shipSize as my base size?
Next, how do i permute them in the array?

First integer of input refers to the total weight the ship can carry. Second integer refers to the number of cargo present and the rest of the integers represents the individual weight of the cargo
For output, all integers except the last are the individual weight of the cargo in order of their previous input and the final integer represents the total weight
Input 99 7 50 40 2 3 8 13 24
Output 50 40 8 98

lowercase baba
Posts: 12745
51

The first thing you need to do is explain your algorithm for loading the ship. I don't understand why you selected "50 40 8". Why isn't it "7 50 40 97" or "7 2 3 8 13 24 40".

In other words, you need to first explain exactly how you select the cargo containers in English.

benjamin parker
Ranch Hand
Posts: 50

fred rosenberger wrote:Forget about java and recursion.

The first thing you need to do is explain your algorithm for loading the ship. I don't understand why you selected "50 40 8". Why isn't it "7 50 40 97" or "7 2 3 8 13 24 40".

In other words, you need to first explain exactly how you select the cargo containers in English.

The number 7 refers to the number of cargo available.

I have added additional input and output. i'm trying to figure out whats the algo behind it's selection.

benjamin parker
Ranch Hand
Posts: 50

Input 62 7 50 40 2 3 8 13 24
Output 50 3 8 61

Input 23 6 8 12 13 5 6 4
Output 8 5 6 4 23

benjamin parker
Ranch Hand
Posts: 50
any help to guide me? i am trying to find the closest value or equal to my target value.

author
Posts: 23832
140

benjamin parker wrote:any help to guide me? i am trying to find the closest value or equal to my target value.

To be blunt... you never answered Fred question. Fred asked how does your algorithm works -- and not for more examples (so that presumable, we can figure it out for you), or for an explanation of the goal, which has little to do with the algorithm.

Simply, if you can't explain the algorithm to us, how are you going to code the algorithm into the computer?

Henry

benjamin parker
Ranch Hand
Posts: 50

Henry Wong wrote:

benjamin parker wrote:any help to guide me? i am trying to find the closest value or equal to my target value.

To be blunt... you never answered Fred question. Fred asked how does your algorithm works -- and not for more examples (so that presumable, we can figure it out for you), or for an explanation of the goal, which has little to do with the algorithm.

Simply, if you can't explain the algorithm to us, how are you going to code the algorithm into the computer?

Henry

The goal of this problem is to get the closest or equal to the target value and not arranging any of the inputs
1) for every integer, carry out recursion for 2 cases. One is taking into account of the integer and and second is not taking into the account of the integer. [when recursion ends, i will have 2^N cases where N refers to the number of integer inputs ]
2) when current index is greater than array size & sum<taraget =>get the difference between the target value and the computed sum and stored as bestSum
3) compare with all the other test cases, the one with the smallest bestSum is reflected as the output

Bartender
Posts: 1952
7
If the weight is the only constraint this seems like a "straightforward" version of a knapsack problem. The obvious way to come to a possible solution recursively would be to implement a recursive backtracking algorithm. The Wikipedia articles I linked to would be a good place to start looking for information.

benjamin parker
Ranch Hand
Posts: 50

Jelle Klap wrote:If the weight is the only constraint this seems like a "straightforward" version of a knapsack problem. The obvious way to come to a possible solution recursively would be to implement a recursive backtracking algorithm. The Wikipedia articles I linked to would be a good place to start looking for information.

how do i implement the backtracking part? i know that once my current index > the array size, i have to do it.

Bartender
Posts: 5841
56

benjamin parker wrote:

Henry Wong wrote:

benjamin parker wrote:any help to guide me? i am trying to find the closest value or equal to my target value.

To be blunt... you never answered Fred question. Fred asked how does your algorithm works -- and not for more examples (so that presumable, we can figure it out for you), or for an explanation of the goal, which has little to do with the algorithm.

Simply, if you can't explain the algorithm to us, how are you going to code the algorithm into the computer?

Henry

The goal of this problem is to get the closest or equal to the target value and not arranging any of the inputs
1) for every integer, carry out recursion for 2 cases. One is taking into account of the integer and and second is not taking into the account of the integer. [when recursion ends, i will have 2^N cases where N refers to the number of integer inputs ]
2) when current index is greater than array size & sum<taraget =>get the difference between the target value and the computed sum and stored as bestSum
3) compare with all the other test cases, the one with the smallest bestSum is reflected as the output

Good description. In order to be recursive you will need a new method that will somewhere in the body of the method call itself. If you design a new class that captures the current state (such as array of ints so far, and sum), you can pass that into your recursive method, perform the goals as you describe, and then return a new state if it is better than the one passed in or just return the one passed in.
See what you can do with that and show us your code.

benjamin parker
Ranch Hand
Posts: 50
i'm still unable to solve this.how do i implement the backtracking into recursion

Marshal
Posts: 24473
55
You need to be able to evaluate some value which tells you how good your choice was, for any particular choice of entries. In your example it might be the sum of the numbers you chose, for example. Then you need to evaluate that value for each possible choice and identify the choice with the largest value. Or the smallest value, if your metric works that way.

The recursion works like this: Pick one entry and then find the best combination of the remaining entries. Then pick another entry and find the best combination of the remaining entries. And so on. You'll have values for each of those choices, so you just choose the largest of the values. The recursion terminates when there's only one entry to pick.

benjamin parker
Ranch Hand
Posts: 50

Paul Clapham wrote:You need to be able to evaluate some value which tells you how good your choice was, for any particular choice of entries. In your example it might be the sum of the numbers you chose, for example. Then you need to evaluate that value for each possible choice and identify the choice with the largest value. Or the smallest value, if your metric works that way.

The recursion works like this: Pick one entry and then find the best combination of the remaining entries. Then pick another entry and find the best combination of the remaining entries. And so on. You'll have values for each of those choices, so you just choose the largest of the values. The recursion terminates when there's only one entry to pick.

i would like to bruteforce everything and store them inside the arraylist. Once it's done i i will call another function to get the best case in the arraylist. can't seem to do that, is there something wrong with my basecase? also the main idea i am unsure is the backtracking part, how do i make it go back one step and try with cases when the integer is not taken into account

Paul Clapham
Marshal
Posts: 24473
55

benjamin parker wrote:i would like to bruteforce everything and store them inside the arraylist.

What's "everything" and what's "them" and what arraylist is that?

If you're given for example 8 numbers then there are 256 ways to choose a subset of those 8 numbers. Does "them" refer to the 256, or what? Basically you're going to have to produce a better description of your approach than what you did there.

fred rosenberger
lowercase baba
Posts: 12745
51

benjamin parker wrote:i would like to bruteforce everything and store them inside the arraylist. Once it's done i i will call another function to get the best case in the arraylist. can't seem to do that, is there something wrong with my basecase? also the main idea i am unsure is the backtracking part, how do i make it go back one step and try with cases when the integer is not taken into account

Brute force is not really a good way to approach a problem like this. It is conceivable you may have 100 possible containers to load, giving you something like 1267650600228229401496703205375 possible ways to load the boat. It will take you a LONG time to brute force that.

benjamin parker
Ranch Hand
Posts: 50

Paul Clapham wrote:

benjamin parker wrote:i would like to bruteforce everything and store them inside the arraylist.

What's "everything" and what's "them" and what arraylist is that?

If you're given for example 8 numbers then there are 256 ways to choose a subset of those 8 numbers. Does "them" refer to the 256, or what? Basically you're going to have to produce a better description of your approach than what you did there.

the arraylist contains the result and the total sum.

result meaning the list of numbers that are calculated into the total sum.

benjamin parker
Ranch Hand
Posts: 50
i need help in the recursion part. i am only able to go 1 direction

Ranch Hand
Posts: 37
I didn't understood what creator of topic wants.

benjamin parker
Ranch Hand
Posts: 50

Josh Borg wrote:I didn't understood what creator of topic wants.

to find the subset sum that is closest or equal to my original sum

Carey Brown
Bartender
Posts: 5841
56

benjamin parker wrote:i need help in the recursion part. i am only able to go 1 direction

You have some of this right. You are passing in a current combination state in 'result' and then creating a new String when you call BestComb() again.

Instead of index+1 you'll need a loop that goes through all remaining array elements and call BestComb() for each of them.

You can shorted the amount of combos that you try by not calling BestCombo() if the sum will be over capacity.

You can clean up your code a lot by using some static member variables instead of continually passing in things that don't change.

 On top of spaghetti all covered in cheese, there was this tiny ad: how do I do my own kindle-like thing - without amazon https://coderanch.com/t/711421/engineering/kindle-amazon