3
$\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

$\endgroup$
11
  • $\begingroup$ This is easily shown to still be NP-hard. Are you looking for pseudo-polynomial time algorithms? $\endgroup$
    – Steven
    Apr 3, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 21:49

2 Answers 2

4
$\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$.
$\endgroup$
4
  • $\begingroup$ +1, you have written $W'$ in a couple of places where I think you meant just $W$ though? $\endgroup$ Apr 4, 2020 at 13:12
  • $\begingroup$ Fixed, thanks!$ $ $\endgroup$
    – Steven
    Apr 4, 2020 at 13:24
  • $\begingroup$ Can anyone tell me what does $n(V + 1)$ mean? $\endgroup$
    – Deqing
    Jan 29 at 12:34
  • 2
    $\begingroup$ $n(V+1)$ is the product of the number $n$ with the number $V+1$. $\endgroup$
    – Steven
    Jan 29 at 13:05
2
$\begingroup$

Define a matrix $M$ of size $n \times W \times L$. The entry $M[i][j][k]$ denotes the maximum value of the knapsack when exactly $k$ items are chosen from $\{1,\dotsc,i\}$ and the allowed capacity of the knapsack is $j$.

Final Solution: The value of $M[n][W][L]$ (assuming 1 based indexing).

Induction or DP: $M[i][j][k]$ can be stated in terms of smaller subproblem as follows: $M[i][j][k] = \max\,\{\,M[i-1][j-w_i][k-1] + v_i, \, M[i-1][j][k]\}$.

The first term denotes the scenario when the $i^{th}$ item is chosen in the knapsack, and the second term states the scenario when the $i^{th}$ item is not chosen in the knapsack.

Base Case:

  1. For any entry with $k > i$, $M[i][j][k] = -\infty$ since there are only $i$ available items and the desired quantity is $k$.
  2. For every $j \in \{1,\dotsc,W\}$, $i \in \{1,\dotsc,n\}$, and $k = i$, the value $M[i][j][i] = \sum_{p = 1}^{i} v_p$ if $\sum_{p = 1}^i w_p \leq j$ else $M[p][j][p] = -\infty$. In other words, if there are only $i$ available items and the required quantity is also $i$, then pick all the items in the knapsack if and only if the items satisfy the capacity constraint, i.e., sum of weights of the items is at most $j$.

Running Time: $O(W\cdot L \cdot n)$

$\endgroup$
5
  • $\begingroup$ Thanks! Maybe can be simplified to two matrix: $M[i][j] = \max\,\{\,M'[i-1][j-w_i] + v_i, \, M[i-1][j]\}$, one is for k-1, anther is for k ? $\endgroup$
    – Deqing
    Jan 29 at 13:02
  • 1
    $\begingroup$ @Deqing No. For getting k-1 matrix you would require k-2 matrix, and so on. So, I do not think it can be simplified as of now. $\endgroup$
    – D Goyal
    Jan 29 at 13:17
  • $\begingroup$ @Dequing You mean space complexity? If so, then yes. $\endgroup$
    – D Goyal
    Jan 29 at 13:18
  • $\begingroup$ @InuyashaYagami Good work! I agree this is a valid solution, iff every weight is a nonnegative integer. The existence of non-integer, rational weights increases the running time proportional to the size of the denominator, and irrational weights break it completely. I can't remember anymore, but either before or after I made this post I'd found this solution as well, but it was the problem with fractional weights that led me to using Steven's reduction solving it using branch-and-bound. $\endgroup$
    – Bryce219
    Jan 30 at 13:18
  • $\begingroup$ @Deqing If I understand your attempted simplification correctly, what you did was wrong but your answer was ultimately right; you can solve this problem using a 2d matrix. Steven gave an algorithm that shows that the 3d case can be represented as a modified 2d case. If you're looking for a practical solution to this problem I highly recommend looking into using Steven's reduction. $\endgroup$
    – Bryce219
    Jan 30 at 13:48

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.