The 01 Knapsack Problem, Revisited
When I first started this blog in 2019, one of my first posts was about solving the 01 knapsack problem via dynamic programming. In case you need a refresher, my past post contains a succinct description of the problem. Looking back at that post now, however, I have regrets about some of the technical aspects I presented. In this post, I attempt to reconcile those regrets by presenting a cleaner implementation of the dynamic programming method. I also discuss an interesting variant of the standard 01 knapsack problem in which the number of items in the backpack must be even, a generalization of that variant, and how to solve both.
Standard 01 Knapsack
In this post, we consider the “binary” or “01” variant of the knapsack problem:
In this formulation we consider $n$ items, which we enumerate from $0$ to $n1$ to mirror Python’s $0$based indexing. For given $a_i \ge 0$, $b \ge 0$, and $c_i \ge 0$, the optimal objective value may be found by computing $Z(n1, b)$ where
This scheme may be implemented quite easily in Python. For dynamic programming in general, it is
typically useful to incorporate memoization. In
Python, memoization may be implemented simply using functools.cache
(available in Python 3.9+)
as a decorator:
1from functools import cache


Of course, knowing the optimal objective value is not terribly useful without also knowing an
optimal solution that attains it. Below, we improve our function by incorporating a generator
function $X(i, j)$ that churns out the 01 solution based on the relative value of omitting or
retaining an item. We then modify knapsack
to return both the optimal objective value and
identified optimal solution:


Because we memoized the value function $Z(i, j)$, computing X_opt
is remarkably inexpensive
given that all pertinent $Z(i, j)$ are already cached from having computed Z_opt
. Now let’s give
it a try.


01 Knapsack with Even/Odd Stipulation
A few years ago, I came across an exercise involving a variant of the standard 01 knapsack problem with an additional stipulation – the number of items put in the knapsack must be even. Tricky! If you search for the solution to this variant on the Internet, most answers involve defining a pair of value functions
Here, $Z_\text{even}(i, j)$ represents the value that may be garnered from items $0$ through $i$ given a knapsack already holding an even number of items and $j$ capacity remaining. The function $Z_\text{odd}(i, j)$ represents the same but for a knapsack already holding an odd number of items. In each max function, the value of omitting an item requires an evaluation of the same value function since the number of items already in the knapsack remains the same. The value of putting an item in the knapsack, however, requires an evaluation of the alternate function since the number of items changes from even to odd or vice versa. Aside from there being two value functions, the main difference between this variant and the standard knapsack problem is that $Z_\text{odd}(i, j) = \infty$ if $i < 0$. That is, if there are an odd number of items in the knapsack and no items left to consider to make the number even, then the solution is infeasible and the objective value is negative infinity.
Clearly, the best objective value for a knapsack that must contain an even number of items is $Z_\text{even}(n  1, b)$. Though less clear, the best objective value for a knapsack that must contain an odd number of items is $Z_\text{odd}(n  1, b)$. Note that between these two value functions, the only base case with a value of zero (corresponding to a feasible solution) is when the knapsack contains an even number of items, the knapsack is not overfilled, and there are no items left to consider. So computing $Z_\text{odd}(n  1, b)$ is like pretending there is already an item in the knapsack before considering items $0$ through $n1$. As such, an odd number of items $0$ to $n1$ must be placed into the knapsack to make the total items (including the pretend item) an even quantity.
Below is our Python implementation.


Note that $x_i = 0, i=0,\ldots,n1$ is always a feasible “even” solution.
The existence of an “odd” solution, however, is not guaranteed. In such a case, our function
returns None
as the solution rather than a list of zeros and ones. Anyway, let’s give our method
a whirl.


We see that the optimal “even” solution is marginally worse than the “odd” solution, and that the “odd” solution is also the optimal solution to the standard 01 knapsack problem.
01 Knapsack with Generalized Modulo Stipulation
Consider that requiring the knapsack to contain either an even or odd number of items is equivalent to requiring, respectively, either $\left(\sum_{i=0}^{n1} x_i\right)~\text{mod}~2 = 0$ or $\left(\sum_{i=0}^{n1} x_i\right)~\text{mod}~2 = 1$. As it turns out, the implementation may be easily modified to accommodate the general condition $\left(\sum_{i=0}^{n1} x_i\right)~\text{mod}~p = q$ by incorporating a third state variable $k$ to keep count of the number of items (modulo $p$) in the knapsack. This gets us back to a single value function that is more similar to that of the standard 01 knapsack problem:
Of course, there are zero items in the knapsack to start, so the optimal objective value to the formulation above is $Z(n  1, b, 0)$. Now let’s implement this variant in Python.


Let’s test the generalized version to see if it gives the same “even” and “odd” solutions!


Precisely! Let’s additionally compute an optimal solution satisfying the condition $\left(\sum_{i=0}^{n1} x_i\right)~\text{mod}~3 = 1$.


For the given condition, the solution must involve putting 1, 4, 7, 10, or 13 items in the knapsack. Indeed, we see that the optimal solution places 7 items in the knapsack with a combined value of 86.
Summary
Dynamic programming is a powerful tool for solving many types of decision problems. In this post, we showed how dynamic programming may be used to efficiently solve the standard 01 knapsack problem as well as a variant in which the number of items in the knapsack is subject to a modulo condition. Have you encountered similar variants of the 01 knapsack problem? Would you approach the variants I presented differently? Let me know in the comments!
You May Also Like
The 01 Knapsack Problem
The knapsack problem is textbook material in fields like computer …
Optimizing Yield of a Minecraft Farm via SciPy
I do not have much time or interest for playing Minecraft anymore, but …
Leveraging the gurobipypandas Package to Build a Model
As the INFORMS 2023 Annual Meeting comes to an end this week in …