2365. Best Value Within a Capacity

You are given n items. Each item has a weight and a value. Choose any collection of them whose total weight does not go over a capacity, and make the total value as large as you can. Print that largest total value.

Choosing nothing is allowed, so 0 is always achievable and the answer is never negative. Each item may be taken at most once.

## What most people try first

This is the 0/1 knapsack, so the reflex is the table indexed by remaining capacity, filled in O(n * capacity). That is the right algorithm for the version of this problem you have seen before, and it is useless here, for a reason that is entirely about the numbers.

The capacity reaches 4 * 10^10. The table needs one slot per capacity value, so it needs 4 * 10^10 slots. That is not a slow program, it is a program that cannot allocate its own state.

The other reflex is to walk all 2^n collections, which at n = 40 is about 10^12 and far too slow.

Look at which number is small. n is 40. The capacity and the values are enormous. So the exponent gets paid on n, and 2^20 is only a million.

## Halve the item list

Split the items into a left half and a right half of about twenty each. Enumerate every collection of each half, recording for each one its total weight and its total value. Each half gives about a million pairs.

Every collection of the whole list is exactly one left collection together with exactly one right collection, and that correspondence is one-to-one, so the best overall collection is the best such pair and nothing is missed.

## The join needs a running maximum, not just a search

Fix a right collection with weight w and value v. If w is already over the capacity, skip it, since weights are non-negative and a left collection can only add weight. Otherwise there is capacity minus w of room, and you want the left collection with the greatest VALUE among those whose WEIGHT fits in that room.

That is not a plain binary search, and this is the one new idea in the problem. A binary search finds the heaviest left collection that fits, but the heaviest is very often not the most valuable. So sort the left pairs by weight, then walk them once converting each value into the maximum value seen so far at that weight or lighter. Now "best value within this much room" is a binary search for the room followed by a single array read.

## Why the running maximum is correct

After the sweep, entry i holds the best value available among left collections of weight at most the weight at position i. Taking a lighter left collection is always allowed when a heavier one fits, because the weight constraint is an upper bound. So reading the running maximum at the last position that fits considers every left collection that fits, which is exactly the set you are choosing from.

## Overflow

The capacity reaches 4 * 10^10 and so does the total value, both well past the 32-bit signed limit of 2147483647. Weights, values, the capacity, the accumulated totals and the answer all need 64 bits. In C and C++ a 32-bit accumulator wraps quietly here and reports a wrong number without crashing.

## Cost

2^(n/2) to enumerate each half, one sort and one sweep over 2^(n/2) pairs, and one binary search per right collection. A few million steps at n = 40.

## Worked example

``` items (3,4) (4,5) (5,6) (2,3) capacity 10

left half (3,4) (4,5) collections weight 0 value 0 | 3,4 | 4,5 | 7,9 sorted by weight 0:0 3:4 4:5 7:9 running maximum 0:0 3:4 4:5 7:9

right half (5,6) (2,3) collections 0,0 | 5,6 | 2,3 | 7,9

r = (0,0) room 10 heaviest fitting left weight 7, running max 9 total 9 r = (5,6) room 5 heaviest fitting left weight 4, running max 5 total 11 r = (2,3) room 8 heaviest fitting left weight 7, running max 9 total 12 r = (7,9) room 3 heaviest fitting left weight 3, running max 4 total 13

answer 13 ```

### Constraints - 1 <= n <= 40 - 0 <= each weight <= 10^9 - 0 <= each value <= 10^9 - 0 <= capacity <= 4 * 10^10 - The capacity, the weights accumulated and the values accumulated all pass the 32-bit signed limit. Use a 64-bit type throughout.