In the knapsack problem KNAPSACK, the goal is$,$ given a tuple of elements $M=(m_1,...,m_n)$ with weights $W=(w_1,...,w_n)$ and values C$=(c_1,...,c_n),$ and two numbers $U,LinN,$ to decide whether there is a sublist $M^{\text{'}}=(m_{i_1},...,m_{i_l})$ of $M,$ such that

${\displaystyle \underset{j=1}{\overset{l}{}}}{w}_{i_j}U$ and ${\displaystyle \underset{j=1}{\overset{l}{}}}{c}_{i_j}L.$

In this case the instance $(M,W,C,U,L)$ is called solveable.

We now define the problem

KNAPSACK $=\{(M,W,C,U,L)|(M,W,C,U,L)is$ solveable $\}.$

$($a$)$ Prove: KNAPSACK is decideable in time polynomial in $U,L$ and $n$ by a DTM$.$

Hint: Use dynamic programming.

$($b$)$ Prove: KNAPSACK is NP$-$complete.

$($c$)$ Why are the previous two subtasks not contradictory?