0-1 Knapsack Problem¶
Pick the items that gives the most value and fits in the knapsack. This may be formulated as a mixed integer programme like
It can also be formulated as a network problem on a multi-graph with vertices and edges with and where traversal of a regular edge indicates that item is put in the knapsack and an edge indicates not selecting item . The edges are weighted with the item weights and profits and the edges in all have weight and profit equal to 0. The total weight of the path from 1 to vertex must be less than the knapsack capacity .
An example graph with 3 items looks like
The objective is to find a maximum profit path with accumulated weight less than the capacity.
This corresponds to the network model
where are paths in a graph subject to the capacity constraint modeled as a disposable resource with edge consumption for regular edge otherwise 0 and bounds for all .
Such models can be solved directly with the dynamic programming algorithm and when defining the model we need only to define the graph and the resource constraints, see the modeling section.
# 0-1 Knapsack problem
from flowty import Model
# profit and weight per item
p = [10, 13, 18, 31, 7, 15]
w = [11, 15, 20, 35, 10, 33]
c = 47
# multi-graph with edge 'pick'/'pick not' item
es = [
(0, 1),
(1, 2),
(2, 3),
(3, 4),
(4, 5),
(5, 6),
(0, 1),
(1, 2),
(2, 3),
(3, 4),
(4, 5),
(5, 6),
]
# zero profit and weight for 'pick not' edges
ps = [-x for x in p] + [0] * len(w)
ws = w + [0] * len(w)
m = Model()
# specify dynamic programming algorithm
m.setParam("Algorithm", "DP")
g = m.addGraph(obj=ps, edges=es, source=0, sink=6, L=1, U=1, type="B")
m.addResourceDisposable(
graph=g, consumptionType="E", weight=ws, boundsType="V", lb=0, ub=c
)
status = m.optimize()
print(f"ObjectiveValue {round(m.objectiveValue)}")
# get the variable values
for var in m.vars:
if var.x > 0:
print(f"{var.name} = {round(var.x, 1)}")