Quick start#

Get started by defining (or sampling) knapsack problem instances.

Defining a Knapsack Instance#

To solve a knapsack problem, initialise a Knapsack instance with the items and the capacity of the knapsack.

from pykp import Item
from pykp.knapsack import Knapsack


# Define a list of items
items = [
   Item(value=10, weight=5),
   Item(value=15, weight=10),
   Item(value=7, weight=3)
]

# Define knapsack capacity
capacity = 15

# Initialise the Knapsack instance
knapsack = Knapsack(items=items, capacity=capacity)

Solving a Knapsack Instance#

Once initialised, you can solve the knapsack instance using the solve method, which finds the optimal arrangement of items.

# Solve for the optimal solution
knapsack.solve()

# Print the optimal solution's value
print("Optimal solution value:", knapsack.optimal_nodes[0].value)

The solve method offers additional options to identify non-optimal nodes.

  • solve_terminal_nodes: Set to true to compute all terminal nodes.

  • solve_feasible_nodes: Set to true to find all feasible nodes.

  • solve_second_best: Set to true to also find the second-best solution.

Note

Depending on the size of the instance, specifying these options can be computationally expensive.

Example:

# Solve with additional options
knapsack.solve(
   solve_terminal_nodes=True,
   solve_feasible_nodes=True,
   solve_second_best=True
)

Dynamic interactions#

You can also interact with knapsacks dynamically. This is useful to test algorithms for solving the knapsack. You can add or remove items from the knapsack dynamically using the add() and remove() methods. You can empty a knapsack using the empty() method.

# Add an item to the knapsack
knapsack.add(items[0])

# Remove an item from the knapsack
knapsack.remove(items[0])

Visualising Knapsacks#

The Knapsack class provides methods to visualise solution distributions.

  • Plot Terminal Nodes Histogram(): This method plots a histogram of the values for feasible, at-capacity solutions.

knapsack.plot_terminal_nodes_histogram()

Sampling Random Knapsack Instances#

PyKP includes a Sampler class to generate random knapsack problem instances based on defined ranges for densities (item value to weight ratios), and solution values.

from pykp.sampler import Sampler

# Define parameters for the sampler
sampler = Sampler(
    num_items=5,
    normalised_capacity=0.6,
    density_range=(0.5, 1.5),
    solution_value_range=(100, 200)
)

# Generate a sampled knapsack instance
sampled_knapsack = sampler.sample()
print("Sampled knapsack capacity:", sampled_knapsack.capacity)

Saving and Loading Configurations#

You can save and load knapsack configurations in JSON format.

# Save the current knapsack configuration to a JSON file
knapsack.write_to_json("knapsack_config.json")

# Load a knapsack configuration from a JSON file
new_knapsack = Knapsack(
   items=[],
   capacity=0,
   load_from_json=True,
   path_to_spec="knapsack_config.json"
)