Knapsack

This module provides an interface for defining instances of the 0-1 Knapsack Problem.

Example

To define a Knapsack instance, initialise the Knapsack class with Items and a capacity constraint:

from pykp import Knapsack
from pykp 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)

class pykp.knapsack.Knapsack(items: ndarray[Item], capacity: int, load_from_json: bool = False, path_to_spec: str = None)

Bases: object

Represents a knapsack problem solver.

items

An array of items available for the knapsack problem.

Type:

np.ndarray[Item]

capacity

The maximum weight capacity of the knapsack.

Type:

int

state

Binary array indicating the inclusion/exclusion of items in the knapsack.

Type:

np.ndarray

value

The total value of items currently in the knapsack.

Type:

float

weight

The total weight of items currently in the knapsack.

Type:

float

is_feasible

Indicates if the knapsack is within its weight capacity.

Type:

bool

is_at_capacity

Indicates if the knapsack is at full capacity. terminal_nodes (np.ndarray[Arrangement]): An array of all possible arrangements of items that are under the weight constraint, and at full capacity optimal_nodes (np.ndarray[Arrangement]): An array of optimal solutions to the knapsack problem.

Type:

bool

add(item: Item)

Adds the specified item to the knapsack.

Parameters:

item (Item) – The item to be added to the knapsack.

Returns:

The updated knapsack state.

Return type:

np.ndarray

calculate_sahni_k(arrangement: Arrangement)

Calculates the Sahni-k value for a given arrangement.

Parameters:

arrangement (Arrangement) – The arrangement for which to calculate Sahni-k.

Returns:

Sahni-k value.

Return type:

int

empty()

Empties the knapsack by setting all items to be excluded.

Returns:

The updated knapsack state.

Return type:

np.ndarray

load_from_json(path: str)

Loads knapsack instance from a .json file.

Parameters:

path (str) – Filepath to instance .json file.

plot_network() → tuple[Figure, Axes]

Plots a network of knapsack nodes.

Returns:

Figure and Axes objects.

Return type:

tuple[plt.Figure, plt.Axes]

plot_terminal_nodes_histogram() → tuple[Figure, Axes]

Plots a histogram of values for possible at-capacity arrangements.

Returns:

Figure and Axes objects.

Return type:

tuple[plt.Figure, plt.Axes]

remove(item: Item)

Removes the specified item from the knapsack.

Parameters:

item (Item) – The item to be removed from the knapsack.

Returns:

The updated knapsack state.

Return type:

np.ndarray

set_state(state: ndarray)

Sets the knapsack state using the provided binary array.

Parameters:

state (np.ndarray) – Binary array indicating the inclusion/exclusion of items in the knapsack.

Returns:

The updated knapsack state.

Return type:

np.ndarray

solve(solve_terminal_nodes: bool = False, solve_feasible_nodes: bool = False, solve_all_nodes: bool = False, solve_second_best: bool = False)

Solves the knapsack problem and returns optimal arrangements.

Parameters:

• solve_terminal_nodes (bool, optional) – Whether to find all terminal nodes. Default is False. This argument will be deprecated in future versions.

• solve_feasible_nodes (bool, optional) – Whether to find all feasible nodes. Default is False. This argument will be deprecated in future versions.

• solve_all_nodes (bool, optional) – Whether to find all nodes in the knapsack, including terminal nodes, and feasible nodes. Note, this method applies brute-force and may be infeasible for large instances. Default is False.

• solve_second_best (bool, optional) – Whether to find the second best node. Default is False.

Returns:

Optimal arrangements for the knapsack problem.

Return type:

np.ndarray

solve_all_nodes() → ndarray

Computes all nodes in the knapsack problem. Populates attributes nodes, feasible_nodes, terminal_nodes, optimal_nodes.

Returns:

np.ndarray: All nodes in the knapsack problem.

solve_branch_and_bound(solve_second_best: bool)

Solves the optimal and second-best terminal nodes using best-first branch-and-bound.

solve_feasible_nodes() → ndarray

Solves the knapsack problem and returns optimal arrangements. This method will be deprecated in future versions. Use solve with solve_feasible_nodes=True instead.

Parameters:

verbose (bool, optional) – If True, prints the string representation of the knapsack summary. Default is True.

Returns:

Optimal arrangements for the knapsack problem.

Return type:

np.ndarray

solve_terminal_nodes()

Solves the knapsack problem and returns optimal arrangements. This method will be deprecated in future versions. Use solve with solve_feasible_nodes=True instead.

Returns:

Optimal arrangements for the knapsack problem.

Return type:

np.ndarray

summary()

Generates a summary DataFrame containing information about the knapsack state and solutions.

Returns:

Summary DataFrame.

Return type:

pd.DataFrame

write_to_json(path: str)

Writes the knapsack instance to .json.

Parameters:

path (str) – Filepath to output file.