Apply the bottom-up dynamic programming algorithm to the following instance of the knapsack problem where the knapsack c
Posted: Mon May 02, 2022 11:39 am
Apply the bottom-up dynamic programming algorithm to the
following instance of the knapsack problem where the knapsack
capacity W = 4:
Item
Weight
Value
1
2
20
2
1
15
3
1
6
4
2
10
1) Fill the following table:
0
1
2
3
4
0
w1 = 2
v1 = 20
1
w2 = 1
v2 = 15
2
w3 = 1
v3 = 6
3
w4 = 2
v4 = 10
4
2) What is the optimal subset? Write in the corresponding
blank Y if an item is in the optimal
subset and N if it is not in the
subset.
Optimal subset:
Item 1
Item 2
Item 3
Item 4
following instance of the knapsack problem where the knapsack
capacity W = 4:
Item
Weight
Value
1
2
20
2
1
15
3
1
6
4
2
10
1) Fill the following table:
0
1
2
3
4
0
w1 = 2
v1 = 20
1
w2 = 1
v2 = 15
2
w3 = 1
v3 = 6
3
w4 = 2
v4 = 10
4
2) What is the optimal subset? Write in the corresponding
blank Y if an item is in the optimal
subset and N if it is not in the
subset.
Optimal subset:
Item 1
Item 2
Item 3
Item 4