1217. The Largest Total That Stays Under the Cap

There are n positive values and a cap. Choose any subset, including the empty one, and report the largest total that does not exceed the cap.

values 3 4 5 6 7, cap 10 10 3 + 7, or 4 + 6 values 1 2 3 4 5 6 7 8, cap 0 0 only the empty subset fits

## What most people try first

Every subset, all 2^n of them, keeping the best total that fits. At n = 25 that is 33 million subsets and the answer is often found in the first few hundred. A greedy sweep, taking each value if it still fits, is the other instinct and it is wrong: with values 6 4 3 and a cap of 7, greedy takes 6 and stops at 6 while 4 + 3 reaches 7 exactly.

## The two bounds, which do different jobs

Sort the values largest first and precompute the suffix totals, so suffix[i] is the sum of the values from i onward.

The reachability bound. At a node with running total acc and the values from i onward still untouched, the largest total any completion can reach is acc + suffix[i]. If that is at most the best found so far, no completion of this branch can beat the incumbent and the branch is dead. This is the bound that does the work, and it is why the values are sorted: taking the large values first makes acc grow fast, which raises the incumbent early, which makes the bound fire on everything after it.

The exact-hit stop. If the running total equals the cap, the answer is found: nothing can exceed the cap and nothing below it is better. Stop everything. This one changes the best case from exponential to linear on inputs where the cap is reachable, which is most of them.

## What makes a bound sound

A bound is sound when every branch it skips contains no answer better than the one already found. That is the only thing that has to be proved, and it has to be proved rather than felt: a bound that is nearly sound gives a plausible wrong answer, which is the most expensive kind.

The shape of the argument is always the same. Find a quantity that moves in one direction as the search descends, then show that its value at the current node already rules the branch out. If the quantity can move both ways, the bound is not sound however reasonable it looks.

Here the quantity is the running total, which only increases as values are taken, because the values are positive. That is what makes acc + suffix[i] a true ceiling on the branch. With negative values allowed it would not be, and the bound would be unsound; problem #1175 in this bank is the one where negative values are in play, and it is worth comparing.

## Why sorting largest first is not just taste

The bound compares acc + suffix[i] against the incumbent, so it fires more often when the incumbent is already large. Taking the biggest values first produces a large incumbent at the first leaf, which is reached after at most n steps. Sorting smallest first produces a tiny incumbent for a long time and the bound fires on almost nothing. The answer is identical either way, and the running time is not comparable.

## The settled boundaries

A cap of 0 admits only the empty subset, so the answer is 0; that is tested, and it is also the reason the empty subset must be allowed by the statement rather than left ambiguous. A cap at or above the total admits everything, so the answer is the total. When all values are equal to w the reachable totals are the multiples of w, so the answer is the largest multiple of w that is at most min(cap, n * w), which is a closed form the tests check against.

## Cost

Exponential in the worst case, which is a cap just below every reachable total so that nothing hits exactly and the bound rarely fires. On the inputs here it is far less, and the twenty-five value test with a huge cap finishes immediately through the exact-hit stop.

Constraints - `1 ≤ n ≤ 25` - `0 ≤ cap ≤ 10^6` - `1 ≤ each value ≤ 10^5` - the total of all values is below `2.5 * 10^6`, so everything fits in a signed 32-bit integer