The Mixed Integer 01 Knapsack Problem
Note: Thanks to Shraddha Ghatkar for pointing out an error in my implementation that I have since fixed.
Shortly after publishing my last blog post on the 01 knapsack problem, I was privately messaged with a question about using dynamic programming to solve a variant of the standard 01 knapsack problem in which some of the binary variables are relaxed to the unit interval. In this post, I address how to modify the dynamic programming approach to solve this variant.
Standard 01 Knapsack
Recall the formulation of the standard 01 knapsack problem:
This problem may be solved via dynamic programming using the value function
Mixed Integer 01 Knapsack
To formulate the mixed integer variant, we add new continuous variables $y_j, j=0,\ldots,m1$ corresponding to $m$ continuous items. Each item $j$ has size $r_j$ and value $t_j$. The formulation for this variant is
To solve this variant using dynamic programming, we use a very similar value function:
Below, I present a Python implementation of the dynamic programming approach for this problem.
The function knapsack_mixed
takes as arguments the list of discrete item sizes $\boldsymbol{a},$
the list of continuous item sizes $\boldsymbol{r},$ the knapsack capacity $b,$ the list of discrete
item values $\boldsymbol{c},$ and the list of continuous item values $\boldsymbol{t}$.
1from functools import cache
2
3
4def knapsack_mixed(a, r, b, c, t):
5
6 @cache
7 def Z(i, k):
8 if i >= 0 and k >= 0:
9 return max(Z(i  1, k), Z(i  1, k  a[i]) + c[i])
10 elif k < 0:
11 return float('inf')
12 else:
13 Zhat = 0
14 for j in sorted(range(len(r)), key=lambda j: t[j] / r[j], reverse=True):
15 Zhat += t[j] * min(1, k / r[j])
16 k = r[j] * min(1, k / r[j])
17 if k == 0:
18 break
19 return Zhat
20
21 def X_and_Y(k):
22 X_opt = [0] * len(a)
23 for i in range(len(a)  1, 1, 1):
24 X_opt[i] = int(Z(i  1, k  a[i]) + c[i] > Z(i  1, k))
25 k = a[i] * X_opt[i]
26 if k == 0:
27 break
28 Y_opt = [0] * len(r)
29 for j in sorted(range(len(r)), key=lambda j: t[j] / r[j], reverse=True):
30 Y_opt[j] = min(1, k / r[j])
31 k = r[j] * Y_opt[j]
32 if k == 0:
33 break
34 return X_opt, Y_opt
35
36 return Z(len(a)  1, b), *X_and_Y(b)
Below, we split the items from the previous post into discrete and continuous sets (not necessarily in the same order). We then run our dynamic programming implementation to find the optimal solution.


The solution involves putting 6 of the 9 discrete items into the knapsack. Additionally, two of the continuous items are put in their entirety into the knapsack, and twofifths of another continuous item is also put into the knapsack.
Invoking the function with r
and t
as empty lists will produce a solution to a standard 01
knapsack problem. Similarly, invoking the function with a
and c
as empty lists will produce a
solution to the continuous knapsack problem (in which the quantity of each item is bounded to
$[0, 1]$).
You May Also Like
The 01 Knapsack Problem, Revisited
When I first started this blog in 2019, one of my first posts was …
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 …