Knapsack

Efficient implementations of simple branch and bound and dynamic programming algorithms for 0-1 and unbounded Knapsack problems. The purpose of this project is to provide highly optimized and flexible implementations of basic algorithms for solving small to medium instances of Knapsack problems.

Dependencies

Range-v3 (https://ericniebler.github.io/range-v3/)

Build process

The build process requires CMake 3.19 (https://cmake.org/) or more and the Conan C++ package manager (https://conan.io/).

How to Compile

Just

make

Code example

struct Item {
    double cost, value;
};
std::vector<Item> items = ...;
double budget = ...;
...
auto knapsack = knapsack_bnb(budget, items,
        [](const Item & i) {
            return i.value;
        },
        [](const Item & i) {
            return i.cost;
        });

knapsack.solve();
// knapsack.solve(std::chrono::seconds(10)); // or solve with timeout

double solution_value = 0.0;
for(const Item & i : knapsack.solution()) {
    solution_value += i.value;
}