benjamin parker

Ranch Hand

Posts: 50

posted 3 years ago

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

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

posted 3 years ago

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 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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

benjamin parker

Ranch Hand

Posts: 50

posted 3 years ago

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.

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

benjamin parker

Ranch Hand

Posts: 50

posted 3 years ago

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 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

posted 3 years ago

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

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

posted 3 years ago

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.

Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.

benjamin parker

Ranch Hand

Posts: 50

posted 3 years ago

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

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.

posted 3 years ago

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 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.

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

benjamin parker

Ranch Hand

Posts: 50

posted 3 years ago

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.

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

posted 3 years ago

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 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

posted 3 years ago

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.

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.

posted 3 years ago

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.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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

posted 3 years ago

the arraylist contains the result and the total sum.

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

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

benjamin parker

Ranch Hand

Posts: 50

posted 3 years ago

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.
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

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. |