Problem $4.($Worth $3$ points$)$

Consider the knapsack problem from class. There is now an infinite supply of each item, so you

may take as many copies as you like of the same item. Let $n$ be the number of types of items

and let $W$ be the weight that can be held by the bag. All the weights and $W$ are integers. Use

dynamic programming to solve the problem in time $O(n*W).$ Hint: Define $W$ subproblems and

solve each in $O(n)$ time.