We introduced two versions of the Knapsack Problem: one wher…
We introduced two versions of the Knapsack Problem: one where you are trying to fill a knapsack with some subset of n items which cannot be repeated (0/1 version), and another where you assume you have an unlimited supply of every one of the n items that you can put in the knapsack. We called the dynamic programming algorithm for the former Knapsack No Repeat and for the latter, we called it Knapsack Repeat. Let the running time for Knapsack No Repeat be f(n) and let g(n) be the running time for algorithm Knapsack Repeat. Assume both algorithms receive the same set of weights, values and the same capacity. Which one of the following is true: