pykp.solvers.

greedy

pykp.solvers.greedy(items: list[Item], capacity: int) → Solution

Appy the greedy algorithm to a knapsack problem instance.

The greedy algorithm selects the best item at each step based on the value-to-weight ratio, until no more items can be added to the knapsack.

Parameters:

itemsnp.ndarray[Item]

Array of items to consider for the knapsack.

capacityint

Maximum weight capacity of the knapsack.

Returns:

SolutionSolution

The greedy arrangement of items in the knapsack.

Examples

Solve a knapsack problem using the greedy algorithm:

>>> from pykp.knapsack import Item
>>> from pykp import solvers
>>> items = np.array(
...     [
...         Item(value=100, weight=50),
...         Item(value=200, weight=100),
...         Item(value=400, weight=300),
...     ]
... )
>>> capacity = 300
>>> solvers.greedy(items, capacity)
(v: 300, w: 150, s: 6)

Note

The greedy algorithm is not guaranteed to find the optimal solution to the knapsack problem. It is a heuristic algorithm that selects the best item at each step based on the value-to-weight ratio, until no more items can be added to the knapsack.