XII. (22 points) Consider the following items in the Knapsack Problem: 0 1 2 8 !...

Transcribed Image Text:

XII. (22 points) Consider the following items in the Knapsack Problem: 0 1 2 8 ! 0 0 0 3 40 Item 1 2 3 4 (a) $15 (b) $23 (c) $25 (d) $20 In the Fractional Knapsack Problem, what is the maximum value that can be put in the knapsack? P[4][8] = P[4][9] = 0 0 0 0 Using the same items as in part (a), the Dynamic Programming approach outlined in the book and discussed in class produces a (n + 1) x (W+ 1) table containing the maximum values P[i][w] for a knapsack of capacity w, considering the first i items. w → 0 0 1 1 weight 3 6 6 6 6 4 6 12 12 12 2 4 value $6 $12 $1 $4 6 12 12 12 Knapsack capacity W = 9. 6 6 18 18 19 ? 6 6 12 18. 13 18 18 13 18 ? Compute the missing values in this table using the formula outlined in the textbook and in class Starting from the value of P[4][9] (the maximum profit for the 0-1 Knapsack in this case) which items are placed in the knapsack to achieve this maximum value? Using the procedure discussed in class, show how you arrived at your answer. XII. (continued) Using the same items, determine the maximum value in the knapsack if we allow repetitions; i.e., if there are an unlimited number of each item so that more than one such item can be chosen. Find the missing values in the following linear array. P(w) is the maximum profit obtainable for a knapsack of capacity w. 0 1 P(W): 0 0 P(8) = P(9) = 2 3 1 6 W 4 5 6 7 8 9 12 12 13 18 ? ? Which items should be put in the knapsack to achieve the maximum value P(9)? Using the procedure described in class, show how you arrived at your answer. XII. (22 points) Consider the following items in the Knapsack Problem: 0 1 2 8 ! 0 0 0 3 40 Item 1 2 3 4 (a) $15 (b) $23 (c) $25 (d) $20 In the Fractional Knapsack Problem, what is the maximum value that can be put in the knapsack? P[4][8] = P[4][9] = 0 0 0 0 Using the same items as in part (a), the Dynamic Programming approach outlined in the book and discussed in class produces a (n + 1) x (W+ 1) table containing the maximum values P[i][w] for a knapsack of capacity w, considering the first i items. w → 0 0 1 1 weight 3 6 6 6 6 4 6 12 12 12 2 4 value $6 $12 $1 $4 6 12 12 12 Knapsack capacity W = 9. 6 6 18 18 19 ? 6 6 12 18. 13 18 18 13 18 ? Compute the missing values in this table using the formula outlined in the textbook and in class Starting from the value of P[4][9] (the maximum profit for the 0-1 Knapsack in this case) which items are placed in the knapsack to achieve this maximum value? Using the procedure discussed in class, show how you arrived at your answer. XII. (continued) Using the same items, determine the maximum value in the knapsack if we allow repetitions; i.e., if there are an unlimited number of each item so that more than one such item can be chosen. Find the missing values in the following linear array. P(w) is the maximum profit obtainable for a knapsack of capacity w. 0 1 P(W): 0 0 P(8) = P(9) = 2 3 1 6 W 4 5 6 7 8 9 12 12 13 18 ? ? Which items should be put in the knapsack to achieve the maximum value P(9)? Using the procedure described in class, show how you arrived at your answer.

Answer rating: 100% (QA)

Answer Formula miw maxmi1w m1iwwi pi where i is number of items w is column numberweight wi weight o... View the full answer