knapsack_solver

https://github.com/sucanjan/knapsack-solver

This gem contains command-line utility for solving 0/1 knapsack problem using branch-and-bound method, dynamic programming, simple heuristic (weight/price) and fully polynomial time approximation scheme. It can measure CPU and wall-clock time spent by solving a problem, compute relative error of the result and generate graphs from those values.