Consider the 0-1 Knapsack problem where all items have the same benefit of b. In other words, we have n items where w is the weight of the ith item, every item has a benefit of b, and the capacity of the knapsack is W. We want to find a subset of items whose total weight is at most W and whose total benefit is as large as possible. (This is knapsack without repetition; each item can be chosen at most once). (a) What algorithm design paradigm is most appropriate for this problem? Divide and Conquer, Brute Force or Greedy, Dynamic Programming. Why?

(b) Verbally describe an efficient algorithm for this problem.

(c) What is the asymptotic running time of your algorithm?