Consider the following knapsack problem with W = 13: Vi Wi 5 5 4 6 7...

Transcribed Image Text:

Consider the following knapsack problem with W = 13: Vi Wi 5 5 4 6 7 8 7 4 (a) Thinking of the above problem as a fractional knapsack problem and using the optimal greedy approach, give the best possible fractional knapsack problem solution. (b) Considering the same problem but this time as an integer knapsack problem. Make a branch and bound graph as was done in the lectures. Highlight the optimal solution. (c) Let's modify the above problem to the 0-1 integer knapsack problem where you can either take a full item or leave a full item and you only have at most one of any item (in other words, this is the integer knapsack problem where each c; is either 0 or 1). Use the same greedy approach from the previous problem to find a solution. Does this give the optimal solution? Justify your answer by drawing a full backtracking tree of all possibilities. Consider the following knapsack problem with W = 13: Vi Wi 5 5 4 6 7 8 7 4 (a) Thinking of the above problem as a fractional knapsack problem and using the optimal greedy approach, give the best possible fractional knapsack problem solution. (b) Considering the same problem but this time as an integer knapsack problem. Make a branch and bound graph as was done in the lectures. Highlight the optimal solution. (c) Let's modify the above problem to the 0-1 integer knapsack problem where you can either take a full item or leave a full item and you only have at most one of any item (in other words, this is the integer knapsack problem where each c; is either 0 or 1). Use the same greedy approach from the previous problem to find a solution. Does this give the optimal solution? Justify your answer by drawing a full backtracking tree of all possibilities.

Answer rating: 100% (QA)

a In the fractional knapsack problem the optimal greedy approach is to sort items by valuetowei... View the full answer