Week $9$: Unbonded Knapsack Problem

The unbounded knapsack problem $($also known as complete knapsack problem$)$ is a problem which similar to $\frac{0}{1}$ knapsack problem. Given a set of items and capacity of knapsack, asking you to maximizing total value of items that you can keep in the knapsack. The only difference is we restrict the number of item copies or not. In $\frac{0}{1}$ knapsack problem, we can only decide take or not take. In unbounded knapsack problem, we don't restrict the number of item copies, in other words, you can take each item arbitrary non$-$negative integer times. We can define the problem I$/$O as below: $q,$

Instance: candidate items $\{(v_1,w_1),(v_2,w_2),$dots,$(v_n,w_n)\}$ where $(v_i,w_i)$ tuple shows item value and weight for i$-$th item, knapsack capacity $W$

Result: The maximum value $($or possible combination of items$)$ that you can keep in knapsack $q,$

Description

You can design your transition function similar to $\frac{0}{1}$ knapsack problem. Consider capacity $W$ and the item $(v_i,w_i),$ you can peek the item at most $\frac{W}{w_i}$ copies.

Questions

$1$ We can solve above problem by dynamic programming approach, what's the transition function? Please write down your answer in recursively way.

$2$ Traditional DP algorithm will construct an $nW$ table to keep subproblem solutions. We can improve the space complexity by reduce the size of cache table. Please design an algorithm to solving unbounded knapsack problem with space complexity $O(W).$

$3$ Design an algorithm to reconstruct the combination of items with $O(nW)$ table, and analyzing its time complexity.

$4$ Same to Q$3,$ but doing things with $O(W).$

For the implementations please use c$++$ language!