Largest Total Under a Capacity
You are given n weights and a capacity. Choose any collection of the weights, including none of them, so that their total does not go over the capacity. Make that total as large as you can, and print it.
Choosing none of the weights is always allowed, so 0 is always reachable and the answer is never negative. Each weight may be used at most once. Two weights of equal value are two separate weights, and either, both or neither may be chosen.
## What most people try first
Try every collection. There are 2^n of them, and at n = 40 that is about 10^12, which no judge will sit through.
The reflex after that is a subset-sum table indexed by the total, the way a knapsack is usually written. Here that is worse than too slow, it is impossible. The weights reach 10^9 and there are up to forty of them, so the totals reach 4 * 10^10, and no array of that length exists on the machine.
Notice what the two failures have in common. The first is too slow because the ITEM COUNT sits in the exponent. The second does not fit because the VALUES are being used as an index. Forty is a small number and 10^9 is a large one, so the way out is to keep paying an exponent, but on a smaller count.
## Halve the item list
Cut the weights into a left half and a right half of about twenty each. Enumerate every reachable total of the left half, and every reachable total of the right half. Each is about 2^20, which is a million, and that is fine.
Every collection of the whole list is one left collection together with one right collection, and that pairing is exact: a collection has precisely one left part and precisely one right part, never two and never none. So the best answer over all collections is the best answer over all such pairs, and nothing is lost by only looking at pairs.
## The join
Fix a right total r. If r is already over the capacity then no left total can rescue it, because every weight is non-negative and so every left total only adds. Otherwise there is capacity minus r of room left, and you want the largest left total that fits in that room.
Sort the left totals once and that question is a binary search: the last position whose value is at most the room remaining. The empty left collection contributes a total of 0, which always fits, so such a position always exists.
## Overflow
The capacity goes to 4 * 10^10 and so do the totals. That is past 2147483647, the largest signed 32-bit value, so the capacity, every total and every accumulator need a 64-bit type. In C and C++ a 32-bit accumulator wraps quietly to a negative number here and the answer comes out wrong without any crash to point at it.
## Cost
2^(n/2) to enumerate each half, one sort of 2^(n/2) values, and one binary search per right total. At n = 40 that is a few million steps against about 10^12 for walking every collection.
## Worked example
``` weights 3 34 4 12 capacity 10
left half 3 34 reachable totals 0 3 34 37 right half 4 12 reachable totals 0 4 12 16 left totals sorted 0 3 34 37
r = 0 room 10 largest left total <= 10 is 3 pair total 3 r = 4 room 6 largest left total <= 6 is 3 pair total 7 r = 12 over the capacity, skipped r = 16 over the capacity, skipped
answer 7 ```
### Constraints - 1 <= n <= 40 - 0 <= each weight <= 10^9 - 0 <= capacity <= 4 * 10^10 - The capacity and the totals do not fit in a 32-bit signed integer. Use a 64-bit type.