Module knapsack 

0/1 Knapsack and fractional knapsack solvers.

Provides exact DP, greedy heuristic, branch-and-bound, and the classical fractional (continuous) knapsack. Multi-dimensional knapsack is also supported via MultiKnapsackProblem.

Structs

KnapsackItem

A single knapsack item with integer weight and value.

MultiKnapsackItem

An item for the multi-dimensional knapsack.

Functions

fractional_knapsack

Solve the fractional knapsack in O(n log n) via greedy value-density sort.

knapsack_branch_bound

Exact branch-and-bound for 0/1 knapsack with LP-relaxation bounding.

knapsack_dp

Solve the 0/1 knapsack exactly using bottom-up DP in O(n · W) time and space.

knapsack_greedy

Greedy 0/1 knapsack: sort by value/weight ratio and greedily include items.

multi_knapsack_greedy

Multi-dimensional 0/1 knapsack solved by greedy + local search.

Type Aliases

KnapsackResult

Result type for knapsack operations.