please show all work solve on pen and paper
NO CODe
- No Duplicate Answers Please Show All Work Solve On Pen And Paper No Code 1 (137.82 KiB) Viewed 21 times
NO DUPLICATE ANSWERS. please show all work solve on pen and paper NO CODe
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
NO DUPLICATE ANSWERS. please show all work solve on pen and paper NO CODe
NO DUPLICATE ANSWERS.
please show all work solve on pen and paper
NO CODe
(70 pts) Given n=4 objects: ol = (2.56), 02 = (7, 914), 03 = (6, 913), 04 = (4. $2), where two-tuples indicate (weight, profit) and a knapsack with capacity M=9, answer following questions. 2 (15 pts) Solve the 0-1 knapsack problem of the above instance by using the dynamic programming approach explained in the lecture. Show the (n+1) by (M+1) table T[m] constructed by the algorithm and explain the way you derive the solution from the table. b. (10 pts) Solve the fractional knapsack problem of the above instance by using the optimal greedy algorithm leared in the lecture. Show your calculation to derive the maximum profit in details. c. (15 pts) Solve the 0-1 knapsack problem by using the same greedy algorithm you used in b. Show if the resulting selection is optimal or not. Explain your reasoning. d. (15 pts) Solve the 0-1 knapsack problem by using the branch and bound algorithm with depth- first search. Show the pruned state space tree where each node is indicated with total profit, total weight and bound. Note the order that you visit each node and MaxProfit value when it is updated. Mark all non-promising nodes by "X". e. (15 pts) Show the time-complexity of the above three algorithms. Briefly explain why you derive your answers. Discuss whether each algorithm is optimal for the 0-1 knapsack and for the fractional knapsack problems.
please show all work solve on pen and paper
NO CODe
(70 pts) Given n=4 objects: ol = (2.56), 02 = (7, 914), 03 = (6, 913), 04 = (4. $2), where two-tuples indicate (weight, profit) and a knapsack with capacity M=9, answer following questions. 2 (15 pts) Solve the 0-1 knapsack problem of the above instance by using the dynamic programming approach explained in the lecture. Show the (n+1) by (M+1) table T[m] constructed by the algorithm and explain the way you derive the solution from the table. b. (10 pts) Solve the fractional knapsack problem of the above instance by using the optimal greedy algorithm leared in the lecture. Show your calculation to derive the maximum profit in details. c. (15 pts) Solve the 0-1 knapsack problem by using the same greedy algorithm you used in b. Show if the resulting selection is optimal or not. Explain your reasoning. d. (15 pts) Solve the 0-1 knapsack problem by using the branch and bound algorithm with depth- first search. Show the pruned state space tree where each node is indicated with total profit, total weight and bound. Note the order that you visit each node and MaxProfit value when it is updated. Mark all non-promising nodes by "X". e. (15 pts) Show the time-complexity of the above three algorithms. Briefly explain why you derive your answers. Discuss whether each algorithm is optimal for the 0-1 knapsack and for the fractional knapsack problems.