2
$\begingroup$

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

Improve this question
$\endgroup$
11
  • $\begingroup$ This is easily shown to still be NP-hard. Are you looking for pseudo-polynomial time algorithms? $\endgroup$ – Steven Apr 3 '20 at 11:12
  • $\begingroup$ @Steven Yes I am, and while your solution to select at least $L$ items appears to hold, your solution to ensure that you select at most $L$ items doesn't appear to satisfy the condition that the sum of weights of every item selected must be less than $W$; it satisfies this in the transformed case, but not in the original case. $\endgroup$ – Bryce219 Apr 3 '20 at 21:21
  • $\begingroup$ I'm not sure I completely understand the comment. Are you referring to "suppose that each item weighs at most W" in my answer? What I mean is that you can do a preprocessing to discard all these items, and you work through the transformations with the remaining items. $\endgroup$ – Steven Apr 3 '20 at 21:25
  • $\begingroup$ @Steven No, I am referring to the algorithm to ensure that there are at most $L$ items in the knapsack (I interpreted $W$ to be the weight constraint and $L$ to be the item constraint). The algorithm is able to produce solutions in which the weight constraint is violated (not in the transformed case, but in the original untransformed-weight case). I am saying that transforming $W$ to $W+L(W+1)$ and adding $(W+1)$ to every item allows for these weight-violated solutions $\endgroup$ – Bryce219 Apr 3 '20 at 21:35
  • $\begingroup$ Unless I made some mistake, if the weight constraint is violated then the number of selected items must be less than $L$, therefore their total value will be less than $Ln(V+1)$ showing that there is no solution to the original instance (I discuss this in the very last bullet point). Are you saying that there are instances where $L$ items can be select but an optimal set of items for the instance obtained after my transformations violates the weight constraint in the original instance? If so can you post a small example where this happens? $\endgroup$ – Steven Apr 3 '20 at 21:49
3
$\begingroup$

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$.
Improve this answer
$\endgroup$
2
  • $\begingroup$ +1, you have written $W'$ in a couple of places where I think you meant just $W$ though? $\endgroup$ – j_random_hacker Apr 4 '20 at 13:12
  • $\begingroup$ Fixed, thanks!$ $ $\endgroup$ – Steven Apr 4 '20 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.