pykp.metrics.

sahni_k

pykp.metrics.sahni_k(arrangement: Arrangement, capacity: int) → int

Compute the Sahni-k metric for a given knapsack arrangement.

The Sahni-k metric [R32feded6a4ce-1] [R32feded6a4ce-2] is defined as the smallest number of items (k) whose inclusion in the solution is necessary for the greedy algorithm (applied to the remaining items) to yield an optimal solution.

If k equals zero, the Sahni-k algorithm coincides with the greedy algorithm. If k is equal to the number of items in the solution, the algorithm is similar to a brute-force search through the entire search space.

Parameters:

arrangementArrangement

A knapsack arrangement (subset of items) for which to compute Sahni-k.

capacityint

The capacity constraint of the knapsack.

Returns:

int: Sahni-k value.

Examples

>>> from pykp.knapsack import Arrangement
>>> from pykp.knapsack import Item
>>> from pykp import metrics
>>>
>>> items = [Item(10, 5), Item(20, 8), Item(15, 7)]
>>> arr = Arrangement(items=items, state=[1, 0, 1])
>>> metrics.sahni_k(arr, capacity=15)
2