Problem $3(10$ points$)$

Consider the $0-1$ knapsack problem. In class, we developed an algorithm that works in time $O(nW),$ where $n$ is the number of objects and $W$ is the capacity of the knapsack. This algorithm is good if $W$ is small but what happens when $W$ is really big? The running time can become really bad.

In this problem, we will develop an alternative DP algorithm whose running time will be $O(nV),$ where $V$ is the sum of all object values. For this, we define OPT $i,v$ to be the minimum weight of a subset of the items $\{i,i+1,$dots,$n\}$ that achieve value at least $v.$ Answer the following questions:

a$)(1pt)$ Having computed all OPT $i,j$ values, what is the solution of the original problem? Why?

b$)(1$ pt$)$ What is OPT $n+1,v,$ for $0vV?$ Why?

c$)(1pt$ What is OPT $[i,V+1],1in?$ Why?

d$)(3$ pts$)$ Write a recursive formula for OPT $i,v$ in terms of other OPT $[]$ values. Justify how you came up with this expression. Hint. Again consider whether you select object $i$ or not.

e$)(1$ pt$)$ How many subproblems are there overall? Why?

f$)(1$ pt$)$ How do you fill the matrix OPT$[]$ of solutions? Why?

g$)(2$ pts$)$ Describe an algorithm $($in a few lines$)$ that uses the recurrence for OPT $i,v$ to solve this problem with dynamic programming. What will the running time of the resulting algorithm expressed with the $O()$ notation?