• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion  RSS feed

 
benjamin parker
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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



 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
benjamin parker
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Additional input and output


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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
any help to guide me? i am trying to find the closest value or equal to my target value.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Jelle Klap
Bartender
Posts: 1952
7
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i'm still unable to solve this.how do i implement the backtracking into recursion

 
Paul Clapham
Sheriff
Posts: 22841
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 22841
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i need help in the recursion part. i am only able to go 1 direction

 
Josh Borg
Ranch Hand
Posts: 37
Chrome Eclipse IDE Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I didn't understood what creator of topic wants.
 
benjamin parker
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!