Q$3.$ Knapsack Problems $[30$ Points$]$ Recall that in a knapsack problem, given $n$ items of known weights $w_1,$dots,$w_n$ and values $v_1,$dots,$v_n$ 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 $w_{i1}$ and $w_{i2}$ 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?