Answer Happy

Let V[i, j] denote the solution to the subproblem (i, j) of the Knapsack problem when using a bottom up dynamic programming approach, which considers the first items and a knapsack of capacity j. Suppose we want to compute V[5,7] using the previous entries in the dynamic programming table. Moreover, Item i = 5 has weight w5 = 6 and value v5 = = 4. Select the correct statement below. We need both V[4,7] and V[4,3] to compute V[5,7] and moreover, V[5,7] = max{V[4,7], 6+V[4,3]}. We only need V[4,7] to compute V[5,7] and moreover, V[5,7] = V[4,7]. We only need V[4,7] to compute V[5,7] and moreover, V[5,7] = 4+V[4,7]. We need both V[4,7] and V[4,1] to compute V[5,7] and moreover, V[5,7] = max{V[4,7], 4+V[4,1]}. None of the above is correct.