Knapsack Problem with exact required item number constraint

Question

How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight $w$), but you must add exactly $L$ item(s) to the knapsack (and obviously need to optimize the total value of the knapsack).

Every way I've thought of implementing this so far (dynamic programming, brute force) has resulted in either failure, or lifetime-of-universe level computation times. Any help or ideas are appreciated.

Edit: I am looking for pseudo-polynomial time solutions

Answer 1

You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be discarded).

To ensure that you select at least $L$ items:

• Add $n(V+1)$ to the value of every item.
• Now the problem is equivalent to that of maximizing the number of selected items, breaking ties in favor of set of items with largest original total value, subject to weight constraints. There is a solution that selects at least $L$ items iff the optimal solution has a value of at least $n(V+1)L$.

To ensure that you select at most $L$ items:

• Add $(W+1)$ to the weight of every item.
• Add $L(W+1)$ to $W$.
• Now every subset of more than $L$ items weighs at least $(L+1)(W+1) = L(W+1) + (W+1) > L(W+1) + W$, and is hence not feasible. Every subset of $L$ items that had an overall weight of $w$, now weighs $L(W+1) + w$, and hence is feasible iff $w \le W$. A subset with less than $L$ items might be feasible even if its overall weight is more than $W$, however its total value will always be smaller than $n(V+1)L$.