Function ADS::knapsackBB

Function Documentation

inline std::pair<long, Nodes> ADS::knapsackBB(const std::vector<long> &p, const std::vector<long> &v, long C, long *generated = nullptr)

ZAINO by branch-&-bound: the best profit and the objects, by places; the objects by decreasing profit per volume, each in and then out, pruned when the fractional knapsack of the rest does not beat the best.

Pre:

p and v of the same size, p not negative, v positive, C >= 0

Post:

objects within C and their profit