Answer:
See explaination
Explanation:
Given 3 items: {w1 = 1, v1 = 3}, {w2 = 3, v2 = 2}, {w3 = 4, v3 = 3}
Hence OPT(1) = 3, OPT(3) = 2, OPT(4) = 3
Recursive formula for OPT(k) to minimize value is
OPT(k) = INFINITE if k <= 0
= min(3 + OPT(k-1), 2 + OPT(k-3), 3 + OPT(k-4))
Let us calculate OPT(1) to OPT(8)
OPT(1) = 3
OPT(2) = min ( 3 + OPT(1), 2 + OPT(-1), 3 + OPT(-2)) = 6
OPT(3) = 2
OPT(4) = 3
OPT(5) = min ( 3 + OPT(4), 2 + OPT(2), 3 + OPT(1)) = min(6, 8, 6) = 6
OPT(6) = min ( 3 + OPT(5), 2 + OPT(3), 3 + OPT(2)) = min(9, 4, 9) = 4
OPT(7) = min ( 3 + OPT(6), 2 + OPT(4), 3 + OPT(3)) = min(7, 5, 5) = 5
OPT(8) = min ( 3 + OPT(7), 2 + OPT(5), 3 + OPT(4)) = min(8, 8, 6) = 6
