Implementing a Solution(Knapsack Problem) Implementing a solution to the Knapsac
ID: 3682023 • Letter: I
Question
Implementing a Solution(Knapsack Problem)
Implementing a solution to the Knapsack problem is not difficult: it just will take a very long time to run if there are many weights. Here we will describe a recursive approach that you will render into code.
The basic method is the helper method maximize, described here:
The idea is that maximize will solve the knapsack problem for the set of weights weights[0], … , weights[upTo-1] and the limit parameter. Here a description of the method:
If either limit is 0 or upTo is 0, just return 0. In these cases there are either no weights or nothing can be stored.
Try solving the problem without using weight[upTo-1]
maximize will call itself with the same weight and the same limit. The third parameter will be upTo-1.
If the limit is less than weight[upTo-1], just return the value from the previous step immediately.
Otherwise, if the limit is greater than or equal to weight[upTo-1], try using weight[upTo-1] and seeing how much can be packed in using that weight along with others
maximize will call itself passing the weights array, a second parameter computed as the original limit minus weight[upTo-1] , and with the third parameter upTo-1.
In this case, return the larger value from the two approaches.
For convenience, we would use the following method to start off the computation;
This method simply calls the maximize described above with the same weights and limit but with the third parameter the length of the weights array.
Examples
Here are some examples to test with. Of course you can use the five weight example used above as well. The weights have been listed here in a way to use them in an array initializer.
Challenge
The method you will write above is fine but it does not tell you which weights were finally chosen. This challenge problem asks you to correct that by implementing these two methods:
The return type is Set, but you can use ArrayList instead.1 I wanted to copy the headers directly from my code without editing it.
There is no set bonus for this part, but I am open to negotiation .2
Weights Limit Max Pack 19, 30, 130, 137, 173, 182, 209, 225, 259, 260 1082 1082 19, 30, 130, 137, 173, 182, 209, 225, 259, 260 1574 1494 9, 54, 138, 143, 157, 160, 171, 172, 175, 196, 213, 223, 228, 246, 283 2504 2430Explanation / Answer
input.txt
81 : (1,53.38,$45) (2,88.62,$98) (3,78.48,$3) (4,72.30,$76) (5,30.18,$9) (6,46.34,$48)
8 : (1,15.3,$34)
75 : (1,85.31,$29) (2,14.55,$74) (3,3.98,$16) (4,26.24,$55) (5,63.69,$52) (6,76.25,$75) (7,60.02,$74) (8,93.18,$35) (9,89.95,$78)
56 : (1,90.72,$13) (2,33.80,$40) (3,43.15,$10) (4,37.97,$16) (5,46.81,$36) (6,48.77,$79) (7,81.80,$45) (8,19.36,$79) (9,6.76,$64)