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 Knapsack, Item

# 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 accepts an optional method parameter to specify the solver used to solve the instance. Some of these solvers are heuristic solvers, and others are exact solvers. By default, the solver is set to branch_and_bound. The full list of available solvers can be found in pykp.solvers

Note

Depending on the size of the instance, specifying certain solvers can be computationally expensive.

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])

Computational Complexity Metrics#

PyKP provides metrics to evaluate the computational complexity of a knapsack instance. These metrics can be used to approximate the performance of different algorithms across instances. The full list of available metrics can be found in pykp.metrics.

Sahni-k#

The Sahni-k metric is a measure of complexity based on the approximation algorithm proposed by Sahni et al. (1975),[1] and shown to predict human performance on the 0/1 knapsack problem [2]. The metric is defined as the smallest subset of k items that must be selected so that applying the greedy algorithm to the remaining items yields an optimal solution.

For a given set of items and capacity constraint, you can calculate the Sahni-k metric for a knapsack instance using the following code:

from pykp.knapsack import Items
from pykp import metrics

items = [
    Item(value=10, weight=5),
    Item(value=15, weight=10),
    Item(value=7, weight=3)
]
capacity = 15

# Calculate the Sahni-k metric
k = metrics.sahni_k(items, capacity)
print("Sahni-k:", k)

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.

from pykp.sampler import Sampler

# Define parameters for the sampler
sampler = Sampler(
    num_items=5,
    normalised_capacity=0.6,
)

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

Item weights and values are sampled from a uniform distribution by default, but you can customise these distributions by specifying optional parameters to the sampler. The example below defines normal distributions with mean 100 and standard deviation 10 for both weights and values:

# Define custom distribution parameters
 sampler = Sampler(
     num_items=10,
     normalised_capacity=0.5,
     weight_dist=(
         np.random.default_rng().normal,
         {"loc": 100, "scale": 10},
     ),
     value_dist=(
         np.random.default_rng().normal,
         {"loc": 100, "scale": 10},
     ),
 )

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

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"
)

References#