The Knapsack Problem
Table of Contents
The Knapsack Problem(s)
The basic premise of the Knapsack Problem is that we have a knapsack with a maximum capacity (C) and a selection of n items, each item having a weight (\(w_i\)) and a value (\(v_i\)), and we want to pick the items that give us the most total value without exceeding the capacity of our knapsack.
There are two forms of the problem. The first form is what CLRS calls the \(\textit{0-1 Knapsack Problem}\) because we can either take the item (\(1\)) or not take the item (\(0\)) as opposed to the \(\textit{Fractional Knapsack Problem}\) where the "items" are things that we can take fractional portions of (if we're loading up on spices the \(\textit{0-1}\) problem might be pre-packaged spices while the \(\textit{fractional}\) problem involves scooping spices out of the bulk bins).
Although the problems look more or less the same, the fractional problem is one that can be solved using a greedy algorithm while the 0-1 problem can fail if you use a greedy approach so the all-or-nothing version is the more interesting case and the one we'll look at here.
Imports
# python
from collections import namedtuple
from functools import partial
import random
# pypi
from attrs import define
from expects import (be_below_or_equal, contain_exactly, equal, expect,
raise_error)
from joblib import Parallel, delayed
import altair
import numpy
import pandas
# other monkey stuff
from graeae.visualization.altair_helpers import output_path, save_chart
from graeae import Timer
Setup
Solution = namedtuple("Solution", "value inventory count")
TableSolution = namedtuple("TableSolution", "value inventory count table")
NEGATIVE_INFINITY = float("-inf")
TIMER = Timer()
SLUG = "the-knapsack-problem"
OUTPUT_PATH = output_path(SLUG)
save_it = partial(save_chart, output_path=OUTPUT_PATH)
The Brute Force Solution
One way to find the optimal load for our knapsack is to find all the possible loads and taking the best load from those that will fit in the knapsack. This requires us to calculate the values for every subset of items which means we'll have to do \(2^n\) calculations.
An Iterative Brute-Force Version
To have a reference solution I'll make a brute-force iterative version of the knapsack solver. This will have a greater runtime (\(n 2^n\)) but sometimes starting with something easy is useful, even if it's not the solution we ultimately want.
def brute_knapsack(capacity: int, values: list, weights: list) -> Solution:
"""Finds the best selection of items to maximize value
Args:
capacity: maximum weight allowed
values: value for each item available
weights: how much each item weighs
Returns:
best-value, count of each item, count of loops
"""
assert len(values) == len(weights)
number_of_items = len(values)
items = [0] * number_of_items
best_value = 0
count = 0
for combination in range(2**(number_of_items)):
value, weight, carry = 0, 0, 1
for item in range(number_of_items):
increment = items[item] + carry
keep = increment % 2
carry = increment//2
if keep:
value += values[item]
weight += weights[item]
items[item] = keep
count += 1
if weight <= capacity and value > best_value:
best_value = value
solution = items[:]
return Solution(value=best_value, inventory=solution, count=count)
Checking the Brute
def totals(inventory: list, values: list, weights: list) -> tuple:
"""Reduce the inventory values and weights to a total value and a total weight
Args:
inventory: list of item counts
values: list of values for the items
list of weights for the items
Returns:
value, weight for the inventory
"""
value = sum((value for index, value in enumerate(values) if inventory[index]))
weight = sum((weight for index, weight in enumerate(weights) if inventory[index]))
return value, weight
def check_solution(solution: Solution,
expected_inventory: list,
values: list, weights: list, capacity: int):
"""Check that the solution matches the expected
Args:
solution: namedtuple with the knapsack solution
expected_inventory: list of 0's and 1's representing which items to keep
expected_value: total value expected for the solution
values: values for the items
weights: weights for the items
capacity: maximum weight for the knapsack
Raises:
AssertionError if something isn't the expected
"""
expect(solution.inventory).to(contain_exactly(*expected_inventory))
value, weight = totals(solution.inventory, values, weights)
expected_value, expected_weight = totals(expected_inventory, values, weights)
expect(weight).to(be_below_or_equal(capacity))
expect(weight).to(equal(expected_weight))
expect(value).to(equal(expected_value))
return
def check_examples(solver: object) -> None:
"""Check the toy examples
Args:
solver: function to find the optimal knapsack load
"""
# values and weights don't match
# broken = lambda : solver(5, [0, 1], [2, 1, 3])
# expect(broken).to(raise_error(AssertionError))
capacity = 10
values = [42, 12, 40, 25]
weights = [7, 3, 4, 5]
expected = [0, 0, 1, 1]
solution = solver(capacity, values, weights)
check_solution(solution, expected, values, weights, capacity)
capacity = 6
values = [3, 2, 4, 4]
weights = [4, 3, 2, 3]
expected = [0, 0, 1, 1]
solution = solver(capacity, values, weights)
check_solution(solution, expected, values, weights, capacity)
capacity = 18
values = [0, 3, 7, 7, 2, 5, 3, 0]
weights = [4, 4, 6, 6, 1, 5, 2, 5]
expected = [0, 0, 1, 1, 1, 1, 0, 0]
solution = solver(capacity, values, weights)
check_solution(solution, expected, values, weights, capacity)
# this won't work for greedy algorithms
capacity = 10
values = [42, 20, 25, 6]
weights = [7, 4, 5, 6]
expected = [0, 1, 1, 0]
return
check_examples(brute_knapsack)
Let's look at a particular solution.
values = [3, 4, 2, 4]
weights = [4, 2, 3, 3]
capacity = 6
solution = brute_knapsack(capacity=capacity, values=values, weights=weights)
print(f"Call Count: {solution.count}")
print(f"Chosen knapsack value {solution.value}")
print(f"Item inventory: {solution.inventory}")
expect(solution.count).to(equal(len(values) * 2**len(values)))
expect(solution.value).to(equal(8))
expect(solution.inventory).to(contain_exactly(0, 1, 0, 1))
Call Count: 64 Chosen knapsack value 8 Item inventory: [0, 1, 0, 1]
We have a solution that works, but the runtime is \(n2^n\) so let's make a version that does a little better.
A Recursive Exhaustive Search
def exhausted(capacity: int, values: list, weights: list, this_item: int=0) -> Solution:
"""Find the optimal knapsack using an exhaustive search
Args:
capacity: how much weight the knapsack can hold
values: how much the items are worth
weights: hom much the items weigh
this_item: index of the current item in the values and weights
count: number of times this function is called
"""
assert len(values) == len(weights)
next_item = this_item + 1
# quit this branch if the knapsack is already out of space
if capacity == 0:
return Solution(0, [0] * (len(weights) - this_item), 1)
# to save on an extra base-case call handle the last item separately here
if next_item == len(weights):
skip_this_item = Solution(0, [0], 1)
if weights[this_item] > capacity:
return skip_this_item
use_this_item = Solution(value=values[this_item],
inventory=[1], count=1)
return max((skip_this_item, use_this_item), key=lambda x: x.value)
# now on to the recursive cases
descendant_solution = exhausted(this_item=next_item, capacity=capacity,
values=values, weights=weights)
skip_count = descendant_solution.count + 1
skip_this_item = Solution(value=descendant_solution.value,
inventory=[0] + descendant_solution.inventory,
count=skip_count)
if capacity < weights[this_item]:
solution = skip_this_item
count = skip_count
else:
capacity_after_this_item_is_added = capacity - weights[this_item]
descendant_solution = exhausted(
this_item=next_item,
capacity=capacity_after_this_item_is_added,
values=values,
weights=weights)
check_count = skip_count + descendant_solution.count
include_this_item = Solution(value=values[this_item] + descendant_solution.value,
inventory=[1] + descendant_solution.inventory,
count=check_count)
skip_this_item = Solution(value=skip_this_item.value,
inventory=skip_this_item.inventory,
count=check_count)
solution = max((skip_this_item, include_this_item), key=lambda x: x.value)
count = check_count
return solution
check_examples(exhausted)
Checking The Exhaustive
Let's look at that example that we looked at for the iterative brute-force version.
values = [3, 4, 2, 4]
weights = [4, 2, 3, 3]
capacity = 6
solution = exhausted(capacity=capacity, values=values, weights=weights)
brute_solution = brute_knapsack(capacity=capacity, values=values, weights=weights)
print(f"Call Count: {solution.count}")
print(f"Chosen knapsack value {solution.value}")
print(f"Item inventory: {solution.inventory}")
expect(solution.value).to(equal(brute_solution.value))
expect(solution.inventory).to(contain_exactly(*brute_solution.inventory))
Call Count: 12 Chosen knapsack value 8 Item inventory: [0, 1, 0, 1]
So now the number calls has gone down to \(\approx 2^n\), which is better, but not what we want just yet.
Levitin's Memory Function
This is a memoized function that is in Levitin's book. It looks slightly different from the other memoized functions in the other books (but they all look slightly different from each other anyway) but it's only cosmetic. I've been creating the final solution list of items to use in the functions themselves but I'm going to try doing it the way the books do and separate out the solution using a re-creation function afterwards.
Some Pseudocode
The Memoizer
Note: Levitin keeps the weights, values, and solution table in the global space so it doesn't appear in the pseudocode. I'm going to copy that here but change it when I get to implementing it. I'm also going to change the variables a little to get them a little closer to the names I use. I'll call the eternal collections \(\textit{Table, Weights}\), and \(\textit{Values}\).
The \(Table\) is an \(items \times capacity\) table, with from 0 to number of items rows and 0 to the capacity columns. The 0 row and 0 column get initialized with 0 and the other cells with -1. If we have 4 items and a knapsack capacity of 5 we'd have an initial table like this.
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | -1 | -1 | -1 | -1 | -1 |
| 2 | 0 | -1 | -1 | -1 | -1 | -1 |
| 3 | 0 | -1 | -1 | -1 | -1 | -1 |
| 4 | 0 | -1 | -1 | -1 | -1 | -1 |
Where the rows are the items and the columns are the used-capacities for the knapsack.
\begin{algorithm}
\caption{Memory Function Knapsack Solver}
\begin{algorithmic}
\INPUT $i$: the number of the first items to consider.
\INPUT $c$: the knapsack's capacity.
\OUTPUT Value of the optimal subset of the first $i$ items that fit in the knapsack.
\PROCEDURE{MFKnapsack}{$i, c$}
\IF {\textit{Table}$[i, c] < 0$}
\IF {$c < \textit{Weights}[i]$}
\STATE $v \gets $ \textsc{MFKnapsack}($i - 1, c$)
\ELSE
\STATE $v \gets $ \textsc{Max}(\textsc{MFKnapsack}($i - 1, c$), $\textit{Values}[i] + $ \textsc{MFKnapsack}($i - 1, c - \textit{Weights}[i]$))
\ENDIF
\STATE $\textit{Table}[i, c] \gets v$
\ENDIF
\RETURN $\textit{Table}[i, c]$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
To start the function you would pass in the total number of items as the argument for \(i\). Since we initialized the cells (other than the zero row and column) with -1 the initial if is a check to see if the item and capacity passed to the function is already in the table and if it isn't we run the body but if it is we can just return the value from the table.
In the body if the weight of the current item is beyond the remaining capacity of the knapsack we pick the value for the previous item using the current capacity. If the current item will fit in the knapsack then we pick the larger of the previous item's entry with the current capacity and the value of the current item plus the previous item's entry for the current capacity minus the weight of the current item - meaning we pick the bigger of the values we get if we skip this item or keep it.
- If the item and capacity aren't in the table:
- If the item's weight is greater than the remaining capacity use the previous item's value for the current capacity.
- Otherwise use the greater of the previous item's value and this item's value plus the previous item's value for the current capacity minus the current item's weight (the capacity if you use the current item)
- Whichever value you use, set it to the table's entry for this item and the current capacity
- Return the table entry for this item and the current capacity
A Reconstructor
The main algorithm builds a memo-table and returns the value of the optimal solution but doesn't tell you which items are actually taken. For that we'll need a separate function. The pseudocode assumes that the weights (\(w_i\)) and values (\(v_i\)) are global variables.
\begin{algorithm}
\caption{Knapsack Inventory Reconstructor}
\begin{algorithmic}
\INPUT $A$: The table created to solve the knapsack problem
\INPUT $c$: the knapsack's capacity.
\OUTPUT An optimal knapsack solution
\PROCEDURE{KnapsackReconstruction}{$A, C$}
\STATE \( S \gets \emptyset \)
\STATE \(c \gets C \)
\FOR {\(i = n \ldots 1\)}
\IF {\(w_i \leq c\) and \(A[i - 1][c - w_i] + v_i \geq A[i - 1][c]\)}
\STATE \(S \gets S \cup \{i\}\)
\STATE \(c \gets c - w_i\)
\ENDIF
\ENDFOR
\RETURN \(S\)
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
Memory-Function Knapsack
The counts and such are cluttering up the function so I'm going to make this class-based.
@define
class Memorizer:
"""Dynamic Programming solution to the knapsack problem
Args:
capacity: total capacity (by weight) of knapsack
values: values for items to put in knapsack
weights: weights for items to put in knapsack
"""
capacity: int
values: list
weights: list
_items: int=None
_table: list=None
count: int=0
_value: int=None
_inventory: list=None
@property
def items(self) -> int:
"""The number of items available for the knapsack
Raises:
AssertionError: the number of values and weights don't match
Returns:
number of items
"""
if self._items is None:
assert len(self.values) == len(self.weights)
self._items = len(self.values)
return self._items
@property
def value(self) -> int:
"""The total value of the optimal knapsack"""
if self._value is None:
self._value = self.find_value(self.items,
self.capacity)
return self._value
@property
def table(self) -> list:
"""The memo table
Returns:
items + 1 x capacity + 1 list of lists: 0's in 0 column/row, -1 elsewhere
"""
if self._table is None:
first_row = [0] * (self.capacity + 1)
row = [0] + [-1] * self.capacity
table = [row[:] for item in range(self.items)]
self._table = [first_row] + table
return self._table
def find_value(self, item: int, capacity: int) -> int:
"""Find the best total value for the knapsack
Args:
item: the number of the item to use (0...item)
capacity: maximum weight allowed
Returns:
best-value
"""
self.count += 1
# the table is padded
# so we need to adjust the item index for weights, values
this_item = item - 1
if self.table[item][capacity] < 0:
previous_item = item - 1
previous_value = self.find_value(previous_item, capacity)
if capacity < self.weights[this_item]:
value = previous_value
else:
value = max(previous_value,
self.values[this_item] + self.find_value(
previous_item,
capacity - self.weights[this_item]))
self.table[item][capacity] = value
return self.table[item][capacity]
@property
def inventory(self) -> list:
"""Reconstructs the optimal knapsack load using the table
Returns:
inventory of items in the optimal knapsack
"""
if self._inventory is None:
# make sure that the problem has already been solved
self()
self._inventory = [0] * self.items
remaining_capacity = self.capacity
for table_item in range(self.items, 0, -1):
# table_item is padded by one
this_item = previous_table_item = table_item - 1
if (self.weights[this_item] <= remaining_capacity and
self.table[previous_table_item][
remaining_capacity - self.weights[this_item]]
+ self.values[this_item]
>= self.table[previous_table_item][remaining_capacity]):
self._inventory[this_item] = 1
remaining_capacity -= self.weights[this_item]
return self._inventory
def __call__(self) -> int:
"""Finds the best solution:
As a side effect this also sets self.value
Returns:
value for optimal knapsack
"""
return self.value
Check the table maker
capacity, items = 5, 4
values = weights = [0] * items
table = Memorizer(capacity=capacity, weights=weights, values = values).table
# one row per item plus a zero row
expect(len(table)).to(equal(items + 1))
# columns from 0...capacity
expect(len(table[0])).to(equal(capacity + 1))
# first row should be 0's
expect(sum(table[0])).to(equal(0))
# first column should be 0's
expect(sum(row[0] for row in table)).to(equal(0))
# everything else should be -1 (items x capacity sub-array)
expect(sum(sum(row) for row in table)).to(equal(-1 * (items * capacity)))
Check the Final Table
weights = [2, 1, 3, 2]
values = [12, 10, 20, 15]
capacity = 5
memoizer = Memorizer(weights=weights, values=values, capacity=capacity)
memoizer()
expect(memoizer.value).to(equal(37))
expected_table = [[0, 0, 0, 0, 0, 0],
[0, 0, 12, 12, 12, 12],
[0, -1, 12, 22, -1, 22],
[0, -1, -1, 22, -1, 32],
[0, -1, -1, -1, -1, 37]]
for row_index, row in enumerate(memoizer.table):
expect(row).to(contain_exactly(*expected_table[row_index]))
Check the Recovered Solution
Although knowing what the optimal value is for the knapsack is somewhat informative in that it tells us what we can expect to achieve, it isn't really the solution since we don't know what items actually give us this value, so we're going to need to reconstruct it from the table.
weights = [2, 1, 3, 2]
values = [12, 10, 20, 15]
capacity = 5
solution = Memorizer(capacity=capacity, values=values, weights=weights)
expect(solution.inventory).to(contain_exactly(1, 1, 0, 1))
Check It Against The Examples
values = [3, 4, 2, 4]
weights = [4, 2, 3, 3]
capacity = 6
solution = Memorizer(capacity, values, weights)
print(f"Chosen knapsack value {solution.value}")
print(f"Item inventory: {solution.inventory}")
print(f"Call Count: {solution.count}")
check_examples(Memorizer)
Chosen knapsack value 8 Item inventory: [0, 1, 0, 1] Call Count: 17
Our solution is correct, but if you count all the function calls, not just the calls where the solution isn't in the table yet, it takes more calls than our exhaustive function.
Compared to the Exhaustive Search
sizes = list(range(2, 61))
# 0 weights break the Memorizer so make sure everything weighs at least 1
values = [random.choices(list(range(1, size)), k=size) for size in sizes]
weights = [random.choices(list(range(1, random.randint(1, size) * size)), k=size)
for size in sizes]
capacities = [sum(random.choices(weight, k=4)) for weight in weights]
capacities_values_weights = list(zip(capacities, values, weights))
with TIMER:
exhaustive_output = Parallel(n_jobs=-1)(
delayed(exhausted)(capacity, values, weights)
for capacity,values,weights in capacities_values_weights)
Started: 2022-07-11 02:35:10.337731 Ended: 2022-07-11 02:50:47.862952 Elapsed: 0:15:37.525221
def memorizer_knapsack(capacity, values, weights):
memorizer = Memorizer(capacity, values, weights)
memorizer()
return memorizer
with TIMER:
memorized_output = Parallel(n_jobs=-1)(
delayed(memorizer_knapsack)(capacity, values, weights)
for capacity,values,weights in capacities_values_weights)
for index, output in enumerate(exhaustive_output):
try:
expect(output.value).to(equal(memorized_output[index].value))
capacity, value, weight = capacities_values_weights[index]
b_value, b_weight = totals(output.inventory,
value,
weight)
m_value, m_weight = totals(memorized_output[index].inventory,
value,
weight)
expect(m_value).to(equal(b_value))
expect(m_weight).to(be_below_or_equal(capacity))
except AssertionError as error:
c, v, w = capacities_values_weights[index]
print(f"Index: {index}")
print(error)
print(f"Brute: {brute_knapsack(c, v, w)}")
raise
Started: 2022-07-11 05:00:50.158584 Ended: 2022-07-11 05:00:52.849549 Elapsed: 0:00:02.690965
frame = pandas.DataFrame({"Items": sizes,
"Exhaustive": [
solution.count
for solution in exhaustive_output],
"Memoized": [
solution.count
for solution in memorized_output]})
melted = frame.melt(id_vars=["Items"],
value_vars=["Exhaustive", "Memoized"],
var_name="Algorithm", value_name="Calls")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Items",
y="Calls",
color="Algorithm",
tooltip=[altair.Tooltip("Items", format=","),
altair.Tooltip("Calls", format=","),
"Algorithm"],
).properties(
title="Exhaustive vs Memoized Knapsack Solution",
width=800,
height=525
)
save_it(chart, "exhaustive-vs-memoized")
The height of those last points squashes the previous points down to make it look like the two algorithms do about the same until you hit 47 items, but if you trim off those end points you'll see that the exhaustive algorithm generally requires much more calls than the memoized version. The points aren't on a smooth line as a function of the number of items because whenever an item won't fit in the remaining capacity of the knapsack we skip the second recursive call.
UPPER_BOUND = 47
trimmed = melted[melted.Items < UPPER_BOUND]
chart = altair.Chart(trimmed).mark_line(point=True).encode(
x="Items",
y="Calls",
color="Algorithm",
tooltip=[altair.Tooltip("Items", format=","),
altair.Tooltip("Calls", format=","),
"Algorithm"],
).properties(
title=f"Exhaustive vs Memoized Knapsack Solution (< {UPPER_BOUND})",
width=800,
height=525
)
save_it(chart, "exhaustive-vs-memoized-trimmed")
Dynamic Programming
This is taken from Algorithms Illuminated Part 3.
Some Pseudocode
\begin{algorithm}
\caption{Dynamic Programming Knapsack Solver}
\begin{algorithmic}
\INPUT Item Values: \(v_1, v_2, \ldots, v_n\)
\INPUT Item Weights: \(w_1, w_2, \ldots, w_n\)
\INPUT Knapsack Capacity \(C\)
\OUTPUT Subset \(S\) of items with maximum possible sum of values and size at most \(C\)
\PROCEDURE{DynamicKnapsack}{\(v, w, C\)}
\STATE \(A \gets (n + 1) \times (c + 1)\) two dimensional array.
\FOR {\(c \in \{0 \ldots C\}\)}
\STATE \(A[0][c] \gets 0\)
\ENDFOR
\FOR {\(i \in \{1 \ldots n\}\)}
\FOR {\(c \in \{0 \ldots C \}\)}
\IF {\(w_i > C \)}
\STATE \(A[i][c] \gets A[i - 1][c]\)
\ELSE
\STATE \(A[i][c] \gets \)\textsc{Max}(\(A[i - 1][c], A[i - 1][c - w_i] + v_i\))
\ENDIF
\ENDFOR
\ENDFOR
\RETURN \(A[n][C]\)
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
This looks pretty much like the memoized-recursive version so it shouldn't be too hard to understand.
In Python
@define
class CaptainDynamic(Memorizer):
"""Dynamic Programming solution to the knapsack problem
Args:
capacity: total capacity (by weight) of knapsack
values: values for items to put in knapsack
weights: weights for items to put in knapsack
"""
@property
def value(self) -> int:
"""The total value of the optimal knapsack"""
if self._value is None:
self._value = self.find_value()
return self._value
def find_value(self) -> int:
"""Finds the optimal value"""
for item_row in range(1, self.items + 1):
previous_item = this_item = item_row - 1
for capacity in range(self.capacity + 1):
skip_this_item = self.table[previous_item][capacity]
if self.weights[this_item] > capacity:
self.table[item_row][capacity] = skip_this_item
else:
use_this_item = (
self.table[previous_item][
capacity - self.weights[this_item]] +
self.values[this_item])
self.table[item_row][capacity] = max(
(skip_this_item, use_this_item)
)
self.count += 1
return self.table[self.items][self.capacity]
Check the table maker
capacity, items = 5, 4
values = weights = [0] * items
table = CaptainDynamic(capacity=capacity, weights=weights, values = values).table
# one row per item plus a zero row
expect(len(table)).to(equal(items + 1))
# columns from 0...capacity
expect(len(table[0])).to(equal(capacity + 1))
# first row should be 0's
expect(sum(table[0])).to(equal(0))
# first column should be 0's
expect(sum(row[0] for row in table)).to(equal(0))
# everything else should be -1 (items x capacity sub-array)
expect(sum(sum(row) for row in table)).to(equal(-1 * (items * capacity)))
Check the Recovered Solution
Although knowing what the optimal value is for the knapsack is somewhat informative in that it tells us what we can expect to achieve, it isn't really the solution since we don't know what items actually give us this value, so we're going to need to reconstruct it from the table.
weights = [2, 1, 3, 2]
values = [12, 10, 20, 15]
capacity = 5
solution = CaptainDynamic(capacity=capacity, values=values, weights=weights)
expect(solution.inventory).to(contain_exactly(1, 1, 0, 1))
m_solution = Memorizer(capacity=capacity, values=values, weights=weights)
expect(m_solution.inventory).to(contain_exactly(1, 1, 0, 1))
Check It Against The Examples
values = [3, 4, 2, 4]
weights = [4, 2, 3, 3]
capacity = 6
d_solution = CaptainDynamic(capacity, values, weights)
print("Captain Dynamic")
print(f"Chosen knapsack value {d_solution.value}")
print(f"Item inventory: {d_solution.inventory}")
print(f"Call Count: {d_solution.count}")
check_examples(CaptainDynamic)
print("\nMemorizer")
m_solution = Memorizer(capacity, values, weights)
print(f"Chosen knapsack value: {m_solution.value}")
print(f"Item inventory: {m_solution.inventory}")
print(f"Call Count: {m_solution.count}")
check_examples(Memorizer)
Captain Dynamic Chosen knapsack value 8 Item inventory: [0, 1, 0, 1] Call Count: 28 Memorizer Chosen knapsack value: 8 Item inventory: [0, 1, 0, 1] Call Count: 17
Our solution is correct, but if you count all the function calls, not just the calls where the solution isn't in the table yet, it takes more calls than our exhaustive function.
Compared
def dynamic_knapsack(capacity, values, weights):
captain = CaptainDynamic(capacity, values, weights)
captain()
return captain
with TIMER:
dynamic_output = Parallel(n_jobs=-1)(
delayed(dynamic_knapsack)(capacity, values, weights)
for capacity,values,weights in capacities_values_weights)
for index, output in enumerate(exhaustive_output):
try:
expect(output.value).to(equal(dynamic_output[index].value))
capacity, value, weight = capacities_values_weights[index]
b_value, b_weight = totals(output.inventory,
value,
weight)
m_value, m_weight = totals(dynamic_output[index].inventory,
value,
weight)
expect(m_value).to(equal(b_value))
expect(m_weight).to(be_below_or_equal(capacity))
except AssertionError as error:
c, v, w = capacities_values_weights[index]
print(f"Index: {index}")
print(error)
print(f"Brute: {brute_knapsack(c, v, w)}")
raise
Started: 2022-07-11 05:08:19.593276 Ended: 2022-07-11 05:08:21.585963 Elapsed: 0:00:01.992687
frame = pandas.DataFrame({"Items": sizes,
"Dynamic": [
solution.count
for solution in dynamic_output],
"cN": [
solution.capacity * solution.items
for solution in dynamic_output],
"Memoized": [
solution.count
for solution in memorized_output]})
melted = frame.melt(id_vars=["Items"],
value_vars=["Dynamic", "Memoized", "cN"],
var_name="Algorithm", value_name="Calls")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Items",
y="Calls",
color="Algorithm",
tooltip=[altair.Tooltip("Items", format=","),
altair.Tooltip("Calls", format=","),
"Algorithm"],
).properties(
title="Dynamic vs Memoized Knapsack Solution",
width=800,
height=525
)
save_it(chart, "dynamic-vs-memoized")