The answer box shows a DP table for a particular instance of a knapsack problem, with knapsack capacity varying horizont

[answerhappygod]

The Answer Box Shows A Dp Table For A Particular Instance Of A Knapsack Problem With Knapsack Capacity Varying Horizont 1 (295.07 KiB) Viewed 17 times

The answer box shows a DP table for a particular instance of a knapsack problem, with knapsack capacity varying horizontally and the number of allowed items (n) varying vertically. The weight, w, of each item is shown in its corresponding row label (except when n = 0, meaning no items are allowed). Item values are not shown. Your task is to determine which items should be placed in the knapsack to maximise its value, and the values of each of those selected items. You do this by clicking the checkbox for each used item and entering its value in the Value column. Values are required and enabled only for the selected items. Notes • You must follow the algorithm provided in the lecture notes for tracing back to find the solution. • You should be looking at a table where the last two columns are headed "Used?" and "Value". If not (presumably because you have very limited screen space), you will need to zoom out. Answer: (penalty regime: 0, 10, 20, ... %) Capacity 0 1 2 3 4 5 6 7 8 9 10 11 Used? Value n=0 0 0 0 0 0 0 0 0 0 0 0 0 n=1, w=5 0 0 0 0 0 20 20 20 20 20 20 20 0 n=2, w=3 0 0 0 15 15 20 20 20 35 35 35 35 O n=3, w=6 0 0 0 15 15 20 26 26 35 41 41 46 n=4, w=3 0 0 0 19 19 20 34 34 39 45 45 54 U n=5, w=3 0 0 0 19 19 20 34 34 39 45 45 54 U