Week $8$: $0/1$ Knapsack Problem

Given a set of items $x=\{x_1,x_2,$dots,$x_n\}$ and capacity $C.$ We know the weight and value of each item, denoted by $W(x_i)$ and $V(x_i).$ The problem is to find a set $Y=\{y_1,y_2,$dots,$y_m\}subex$ that $W(Y)={\displaystyle \underset{\text{y}\text{i}\text{i}\text{n}\text{Y}}{\overset{?}{}}}W(y_i)C$ and maximize $V(Y)={\displaystyle \underset{\text{y}\text{i}\text{i}\text{n}}{\overset{?}{}}}V(y_i).$

Instance: Capacity $C$ and

a set of items $x=\{(W(x_1),V(x_1)),(W(x_2),V(x_2)),$dots,$(W(x_n),V(x_n))\}.$

Result: A subset Ysubex that $W(Y)C$ and maximize $V(Y).$

Description

We can define the $\frac{0}{1}$ knapsack problem as a function $f(C,x)=Y.$

If we have no capacity or have no item can take, we take nothing, respectively, $f(C,x)=\{\}.$

We can denote prefix subset by $x_i=\{x_1,x_2$dots,$x_i\}subex.$

Consider $f(C,x_i),$ if optimal solution is to take $x_i,$ then $f(C,x_i)=\{x_i\}f(C-W(x_i),x_{i-1})$; If not to take $x_i$ is better, than $f(C,x_i)=f(C,x_{i-1}).$

Thus, $f(c,x_i)=\{\begin{array}{ccc}\{\},& c0or& x_i=\{\}\\ \{x_i\}f(C-W(x_i),& x_{i-1}),V(\{x_i\}F(C-W(x_i),x_{i-1}))>V(f(C,& x_{i-1}))\\ f(C,& x_{i-1}),V(\{x_i\}F(C-W(x_i),x_{i-1}))V(f(C,& x_{i-1}))\end{array}$

Questions

Analyze space and time complexity of a recursive implementation without cache.

Design a table to cache the answer of subproblems.

Analyze space and time complexity of implementation at Q$2.$

Please explain why the algorithm is a pseudo polynomial time algorithm $($kind of exponential time algorithm$),$ not a polynomial time algorithm.