Function ADS::bottino

Function Documentation

inline std::optional<std::vector<int>> ADS::bottino(const std::vector<long> &P)

bottino(): the thief of each jewel of price P[ i ], so that the three thieves take m / 3 each, or nothing; S[ i ][ j ][ h ] tells whether the first i jewels give j to the first and h to the second thief, and the prices are positive, so that j and h range in [ 0 , m / 3 ]; O( n m^2 ) time (exercise 19.5)

Pre:

the prices are not negative

Post:

an assignment returned gives a third of the value to each thief