Which items to pack

Each item is (weight, value), with whole-number weights. Choose items whose weights add up to at most cap and whose values add up to as much as possible. Each item can be taken at most once. Return the positions of the chosen items in items, as a list in any order.

pack([(3, 4), (4, 5), (2, 3)], 7)   # [0, 1]
# weight 3 + 4 = 7, value 4 + 5 = 9
pack([(5, 10)], 4)                  # []

When several choices have the best value, any of them is accepted. The tests check the facts of your answer: every position is valid and used once, the weight fits, and the total value is the best possible.

Limits

• Up to 200 items, with weights from 1 to 100 and cap up to 3,000. Trying every choice (2²⁰⁰ of them, 200 twos multiplied together) is impossible.