Module knapsack 

Knapsack Problem Solvers

This module provides exact and approximate algorithms for several variants of the classical knapsack problem.

Variants

• 0-1 Knapsack (knapsack_dp): Each item can be selected at most once. Solved exactly via dynamic programming in O(n * capacity) pseudo-polynomial time.

• Fractional Knapsack (fractional_knapsack): Items can be taken as fractions. Solved greedily in O(n log n) by sorting on value/weight ratio.

• Bounded Knapsack (bounded_knapsack): Each item has a limited supply count. Reduced to 0-1 knapsack via binary splitting.

• Multi-dimensional Knapsack (multi_dimensional_knapsack): Multiple capacity constraints. Solved via branch-and-bound with LP relaxation.

References

• Martello, S. & Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley.
• Pisinger, D. (1995). “Algorithms for Knapsack Problems.” PhD thesis, DIKU.

Functions

bounded_knapsack

Solve the bounded knapsack problem.

fractional_knapsack

Solve the fractional knapsack problem with a greedy algorithm.

knapsack_dp

Solve the 0-1 knapsack problem with dynamic programming.

multi_dimensional_knapsack

Solve the multi-dimensional 0-1 knapsack problem.