Question

Solve the 0-1 knapsack problem given the following items, each labeled with weight and value. Assume the total weight limit W is 8 lbs. Item 1 Value ($) 8 Weight (lb) 1 23 4 40 30 54 2 6 3

Answer 1

In the 0-1 Knapsack problem, we have to either include an item or not. We cannot include a part of an item, we either include it completely or not at all.

The way to solve this problem is by using the Dynamic programming approach. We see that each item can either be part of the optimal solution or not. So we first find the optimal solution for the same problem with size n-1. Then we add n to its solution and check whether it provides an optimal solution for the problem of size n, or not.

The answer for the above problem will be 94. By the sum of items of weights 6lbs and 2lbs.

item i	1	2	3	4
value val	8	40	30	54
weight wt	1	2	3	6

V[i,w]	w = 0	1	2	3	4	5	6	7	8
i = 0	0	0	0	0	0	0	0	0	0
1	0	8	8	8	8	8	8	8	8
2	0	8	40	48	48	48	48	48	48
3	0	8	40	48	48	70	78	78	78
4	0	8	40	48	48	70	78	78	94

Hope this helps. If you have any queries or suggestions regarding the answers please leave them in the comments section so I can update and improve the answer. Thank you.