pykp.knapsack.

Knapsack#

class pykp.knapsack.Knapsack(items: list[Item], capacity: float)#

Represents a knapsack problem solver.

An instance is defined by a set of items and a capacity constraint. The Knapsack class provides methods to dynamically add or remove items, solve the knapsack problem using different algorithms, and visualise the solution.

A knapsack instance can be initialised with a list of Item objects and a capacity constraint, or by providing a path to a valid JSON specification file.

Parameters:

itemslist of Item: A list of Item objects, each representing a candidate for the knapsack with associated value and weight.
capacityfloat: The maximum total weight allowed in the knapsack.

Attributes:

itemslist of Item: The items in the knapsack.
capacityfloat: The capacity constraint of the knapsack.
statelist of int: A binary array indicating the inclusion/exclusion of items in the knapsack.
valuefloat: The total value of items currently in the knapsack.
weightfloat: The total weight of items currently in the knapsack.
is_feasiblebool: Whether the knapsack is within its weight capacity.
is_at_capacitybool: Whether the knapsack is at full capacity.
optimal_nodeslist of Arrangement: An array of optimal nodes in the knapsack. Optimal nodes are arrangements of items that maximise the total value of items in the knapsack, subject to the weight constraint. Optimal nodes are a subset of terminal_nodes. This attribute is populated after calling the solve method.
terminal_nodeslist of Arrangement: An array of terminal nodes in the knapsack. Terminal nodes are arrangements of items that are under the weight constraint, and at full capacity (no more items can be added without exceeding the capacity constraint). Terminal nodes are a subset of feasible_nodes. This attribute is populated after calling the initialise_graph method.
feasible_nodeslist of Arrangement: An array of feasible nodes in the knapsack. Feasible nodes are arrangements of items that are under the weight constraint. This attribute is populated after calling the initialise_graph method.
nodeslist of Arrangement: An array of all nodes in the knapsack. This attribute is populated after calling the initialise_graph method.
graphnetworkx.DiGraph: A graph representation of the knapsack problem. This attribute is populated after calling the initialise_graph method.

Methods

`add`(item)	Includes a specific item in the knapsack.
`empty`()	Remove all items from the knapsack.
`from_file`(path)	Initialise a knapsack instance from a JSON file.
`initialise_graph`()	Construct a graph representation of the knapsack problem.
`plot_graph`([ax, colour_map, show_legend])	Visualises a graph representation of the knapsack problem.
`plot_terminal_node_hist`([ax])	Plot a histogram of terminal node values.
`remove`(item)	Remove a specific item from the knapsack.
`solve`([method, minizinc_solver])	Solves the knapsack problem to find optimal arrangements.
`summary`()	Return a DataFrame summarising the knapsack instance.
`write_to_json`(path)	Write the knapsack configuration to a JSON file.

Examples

Create a knapsack instance and solve using default settings:

>>> from pykp.knapsack import Knapsack
>>> from pykp.knapsack import Item
>>> items = [
...     Item(value=10, weight=5),
...     Item(value=15, weight=10),
...     Item(value=7, weight=3),
... ]
>>> capacity = 15
>>> knapsack = Knapsack(items=items, capacity=capacity)
>>> knapsack.solve()
>>> print(knapsack.optimal_nodes)
[(v: 25, w: 15, s: 3)]

Solve the knapsack using the branch-and-bound method and explore the optimal nodes:

>>> from knapsack_solver import Item, Knapsack
>>> items = [
...     Item(value=10, weight=10),
...     Item(value=5, weight=5),
...     Item(value=5, weight=5),
... ]
>>> knapsack = Knapsack(items=items, capacity=10)
>>> knapsack.solve(method="branch_and_bound")
>>> print(len(knapsack.optimal_nodes)
2
>>> for arrangement in knapsack.optimal_nodes:
...     print(
...         "Value:",
...         arrangement.value,
...         "Weight:",
...         arrangement.weight,
...         "State:",
...         arrangement.state,
...     )
Value: 10 Weight: 10 State: [1.0 0.0 0.0]
Value: 10 Weight: 10 State: [0.0 1.0 0.0]

Save the knapsack instance to a JSON file:

>>> knapsack.write_to_json("output.json")

Load a knapsack instance from a JSON file:

>>> knapsack = Knapsack.from_file("output.json")