3. Given the following items of the Knapsack problem, write down the dynamic pro
ID: 3580404 • Letter: 3
Question
3. Given the following items of the Knapsack problem, write down the dynamic programming table that contains the solution to the 0-1 Knapsack problem, with maximum weight W of 25 pounds Items: 1: (value: 10, weight = 4) 2: (value: 5, weight = 3) 3: (value: 6, weight = 3) 4: (value: 3, weight = 2) 5: (value: 7, weight = 5) 6: (value: 20, weight = 6) 7: (value: 25, weight = 7) 8: (value: 5, weight = 4) 9: (value: 25, weight = 13) 10: (value: 9, weight = 5) 11: (value: 13, weight = 7) 12: (value: 19, weight = 9) Also, write down the solution to the Knapsack problem.
Explanation / Answer
value=10
weight=4
value=20
weight=6
value=25
weight=7
value=5
weight=4
value=25
weight=13
value=9
weight=5
value=13
weight=7
value=19
weight=9
Items in the solution:
val=9 w=5
val=25 w=7
val=20 w=6
val=6 w=3
val=10 w=4
solution:70
capacity 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 no items 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0value=10
weight=4
0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 value=5 weight=3 0 0 0 5 10 10 10 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 value=6 weight=3 0 0 0 6 10 10 11 16 16 16 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 value=3 weight=2 0 0 3 6 10 10 13 16 16 19 21 21 24 24 24 24 24 24 24 24 24 24 24 24 24 24 value=7 weight=5 0 0 3 6 10 10 13 16 16 19 21 21 24 24 26 28 28 31 31 31 31 31 31 31 31 31value=20
weight=6
0 0 3 6 10 10 20 20 23 26 30 30 33 36 36 39 41 41 44 44 46 48 48 51 51 51value=25
weight=7
0 0 3 6 10 10 20 25 25 28 31 35 35 45 45 48 51 55 55 58 61 61 64 66 66 69value=5
weight=4
0 0 3 6 10 10 20 25 25 28 31 35 35 45 45 48 51 55 55 58 61 61 64 66 66 69value=25
weight=13
0 0 3 6 10 10 20 25 25 28 31 35 35 45 45 48 51 55 55 58 61 61 64 66 67 70value=9
weight=5
0 0 3 6 10 10 20 25 25 28 31 35 35 45 45 48 51 55 55 58 61 61 64 66 68 70value=13
weight=7
0 0 3 6 10 10 20 25 25 28 31 35 35 45 45 48 51 55 55 58 61 61 64 66 68 70value=19
weight=9
0 0 3 6 10 10 20 25 25 28 31 35 35 45 45 48 51 55 55 58 61 61 64 66 68 70Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.