Knapsack Problems $[30$ Points$]$ Recall that in a knapsack problem, given n items of known

weights w$1,...,$ wn and values v$1,...,$ vn and a knapsack of capacity W $,$ we want to find the most valuable

subset of the items that fit into the knapsack. In the $2-$D $($or $2-$dimensional$)$ version of the knapsack

problem, each item i has weights wi$1$ and wi$2$ for two dimensions, and the capacity is now W$1$ and W$2.$

We want to find the most valuable subset of the items that fit into the knapsack $($i$.$e$.,$ do not exceed the

capacity of each dimension$).$

$3\mathrm{.}1[15$ Points$]$ Design a dynamic programming algorithm for the problem $($based on the dynamic

programming discussed in classes$).$ What are the time and space complexities of the algorithm?

$3\mathrm{.}2[15$ Points$]$ Suppose we only care about not exceeding the capacity of any one dimension $($e$.$g$.,$ the

final subset might exceed one dimension but not both$)$ for the $2-$D version of the knapsack problem.

Design a dynamic programming algorithm for this variant. What are the time and space complexities

of the algorithm?

$3\mathrm{.}3[20$ Points $($Honors$)]$ Answer Parts $3\mathrm{.}1$ and $3\mathrm{.}2$ for the k$-$D $($or k$-$dimensional$)$ version of the

knapsack problem, each item i has k weights wi$1,...,$ wik for two dimensions, and the knapsack capacity

is now W$1,...,$ Wk for any k $1.$