Question

Andy is trying to put together a holiday gift knapsack (with W=8) for Sarah. He has n items to choose from, each with infinitely many copies (aka. knapsack with repetitions). Item i has weight wi, and value vi. Andy wants to pick some items (possibility with duplicates) so their total weight is exactly W, while minimizing the total value of the items picked. If OPT(w) denotes the minimum total value needed to make a weight of w, for every 0 ≤ w ≤ W, (i) write the recursive formula for finding OPT(w) and (ii) compute the values of OPT(1) . . . OPT(8) for the following three items: (w1 = 1, v1 = 3), (w2 = 3, v2 = 2), (w3 = 4, v3 = 3).

Answer 1

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