1. The knapsack problem we discussed in class is the following. Given a knapsack

of size M and n items of sizes {a₁, a2,..., an}, determine whether there is a subset S of the

items such that the sum of the sizes of all items in S is exactly equal to M. We assume M

and all item sizes are positive integers.

Here we consider the following unlimited version of the problem. The input is the same as

before, except that there is an unlimited supply of each item. Specifically, we are given n

item sizes a₁, a2,..., an, which are positive integers. The knapsack size is a positive integer

M. The goal is to find a subset S of items (to put in the knapsack) such that the sum of the

sizes of the items in S is exactly M and each item is allowed to appear in S multiple times.

For example, consider the following sizes of four items: {2, 7, 9, 3} and M = 14. Here is a

solution for the problem, i.e., use the first item once and use the fourth item four times, so

the total sum of the sizes is 2+3 × 4 = 14 (alternatively, you may also use the first item 2

times, the second item one time, and the fourth item one time, i.e., 2 ×2+7+3= 14).

Design an O(nM) time dynamic programming algorithm for solving this unlimited knapsack

problem. For simplicity, you only need to determine whether there exists a solution (namely,

you answer is just "yes" or "no"; if there exists a solution, you do not need to report an actual

solution subset).