When I first started this blog in 2019, one of my first posts was about solving the 0-1 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 0-1 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 0-1 Knapsack

In this post, we consider the “binary” or “0-1” variant of the knapsack problem:

In this formulation we consider $n$ items, which we enumerate from $0$ to $n-1$ 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(n-1, 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def knapsack_obj_only(a, b, c):

    @cache
    def Z(i, j):
        if i >= 0 and j >= 0:
            return max(Z(i - 1, j), Z(i - 1, j - a[i]) + c[i])
        elif j < 0:
            return -float('inf')
        else:
            return 0

    return Z(len(a) - 1, b)

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 0-1 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def knapsack(a, b, c):

    @cache
    def Z(i, j):
        if i >= 0 and j >= 0:
            return max(Z(i - 1, j), Z(i - 1, j - a[i]) + c[i])
        elif j < 0:
            return -float('inf')
        else:
            return 0

    def X(i, j):
        if i >= 0 and j >= 0:
            if Z(i - 1, j) > Z(i - 1, j - a[i]) + c[i]:
                yield from [*X(i - 1, j), 0]
            else:
                yield from [*X(i - 1, j - a[i]), 1]

    Z_opt = Z(len(a) - 1, b)
    X_opt = X(len(a) - 1, b)
    return Z_opt, list(X_opt)

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

### data ###
a = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]
b = 30
c = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]

### dynamic programming ###
print(knapsack_obj_only(a, b, c))
print(*knapsack(a, b, c))

### print output ###
# 90
# 90 [1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1]

0-1 Knapsack with Even/Odd Stipulation

A few years ago, I came across an exercise involving a variant of the standard 0-1 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 $n-1$. As such, an odd number of items $0$ to $n-1$ must be placed into the knapsack to make the total items (including the pretend item) an even quantity.

Below is our Python implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def knapsack_even_or_odd(a, b, c, even=True):

    @cache
    def Ze(i, j):
        if i >= 0 and j >= 0:
            return max(Ze(i - 1, j), Zo(i - 1, j - a[i]) + c[i])
        elif j < 0:
            return -float('inf')
        else:
            return 0

    @cache
    def Zo(i, j):
        if i >= 0 and j >= 0:
            return max(Zo(i - 1, j), Ze(i - 1, j - a[i]) + c[i])
        elif j < 0:
            return -float('inf')
        else:
            return -float('inf')

    def Xe(i, j):
        if i >= 0 and j >= 0:
            if Ze(i - 1, j) > Zo(i - 1, j - a[i]) + c[i]:
                yield from [*Xe(i - 1, j), 0]
            else:
                yield from [*Xo(i - 1, j - a[i]), 1]

    def Xo(i, j):
        if i >= 0 and j >= 0:
            if Zo(i - 1, j) > Ze(i - 1, j - a[i]) + c[i]:
                yield from [*Xo(i - 1, j), 0]
            else:
                yield from [*Xe(i - 1, j - a[i]), 1]

    if not isinstance(even, bool):
        raise ValueError('keyword argument \'even\' must be True or False')

    Z_opt = Ze(len(a) - 1, b) if even else Zo(len(a) - 1, b)
    X_opt = Xe(len(a) - 1, b) if even else Xo(len(a) - 1, b
    return Z_opt, None if Z_opt == -float('inf') else list(X_opt)

Note that $x_i = 0, i=0,\ldots,n-1$ 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

### data ###
a = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]
b = 30
c = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]

### dynamic programming ###
print(*knapsack_even_or_odd(a, b, c, even=True))
print(*knapsack_even_or_odd(a, b, c, even=False))

### print output ###
# 89 [1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0]
# 90 [1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1]

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 0-1 knapsack problem.

0-1 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}^{n-1} x_i\right)~\text{mod}~2 = 0$ or $\left(\sum_{i=0}^{n-1} 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}^{n-1} 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 0-1 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def knapsack_modulo(a, b, c, p, q):

    @cache
    def Z(i, j, k):
        if i >= 0 and j >= 0:
            return max(Z(i - 1, j, k % p),
                       Z(i - 1, j - a[i], (k + 1) % p) + c[i])
        elif j < 0:
            return -float('inf')
        else:
            return 0 if k == q else -float('inf')

    def X(i, j, k):
        if i >= 0 and j >= 0:
            if Z(i - 1, j, k) > Z(i - 1, j - a[i], k + 1) + c[i]:
                yield from [*X(i - 1, j, k % p), 0]
            else:
                yield from [*X(i - 1, j - a[i], (k + 1) % p), 1]

    Z_opt = Z(len(a) - 1, b, 0)
    X_opt = X(len(a) - 1, b, 0)
    return Z_opt, None if Z_opt == -float('inf') else list(X_opt)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

### data ###
a = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]
b = 30
c = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]

### dynamic programming ###
print(*knapsack_modulo(a, b, c, 2, 0))
print(*knapsack_modulo(a, b, c, 2, 1))

### print output ###
# 89 [1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0]
# 90 [1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1]

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

1
2
3
4
5
6
7
8
9

a = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]
b = 30
c = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]

### dynamic programming ###
print(*knapsack_modulo(a, b, c, 3, 1))

### print output ###
# 86 [1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0]

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 0-1 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 0-1 knapsack problem? Would you approach the variants I presented differently? Let me know in the comments!