Function ADS::knapsackBacktrack

Function Documentation

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

ZAINO by backtracking with the simple bound: the objects in their order, each in and then out, an object that does not fit skipped, and a node pruned when its profit plus the profits of all the objects still to decide does not beat the best; the nodes generated go to *generated.

Pre:

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

Post:

objects within C and their profit