items is a list of { weight, value, count } objects: there are count copies of that item, and you may take any number of them from 0 to count. The bag holds at most capacity total weight. Return the largest total value.
- Weights are positive integers,
count can be as large as a million - Expanding every item into
count separate 0/1 items is too slow when counts are large - Split each count into the pieces 1, 2, 4, ... and a remainder, and treat every piece as a 0/1 item
- Target complexity: O(Σ log count · capacity) time, O(capacity) space