Best Value Under Two Limits
You are given n items, each with a weight and a value, a weight capacity, and a limit k on how many items you may take. Choose a collection whose total weight does not go over the capacity and which uses at most k items, and make the total value as large as you can. Print that largest value.
Choosing nothing is allowed, so 0 is always achievable. Each item may be taken at most once.
## What most people try first
This is the previous capacity problem with a second constraint bolted on, and that is exactly why it is here. The natural first move is to reuse the running-maximum trick unchanged: sort the left collections by weight, sweep the values into a running maximum, binary search for the room.
That is wrong, and the reason is worth sitting with. The running maximum answers "the best value among left collections of weight at most this much". But the best such collection might use fifteen items, and if the right collection already used ten, then fifteen is not allowed. The running maximum has thrown away the information you now need, so the answer it gives can be unachievable.
Walking all 2^n collections is about 1.7 * 10^10 at n = 34, too slow. A table indexed by capacity cannot be built, since the capacity reaches 3.4 * 10^10.
## Halve the item list, then keep one table per item count
Split into halves of about seventeen. Enumerate each half into (weight, value, count) triples.
Now instead of one sorted table, build ONE TABLE PER LEFT ITEM COUNT. Table number c holds only the left collections that use exactly c items, sorted by weight, with the values swept into a running maximum within that table.
Fix a right collection with weight w, value v and count c. Then for each allowed left count cl from 0 up to k minus c, binary search table cl for the room remaining, read its running maximum, and keep the best total.
## Why this is correct
Splitting by count does not lose anything, because every left collection lands in exactly one table, so looping over the tables for counts 0 through k minus c visits exactly the left collections that are permitted. Within a single table every collection uses the same number of items, so the count constraint is already satisfied and the running maximum over weight is then valid for the same reason it was in the single-constraint version: the weight rule is an upper bound, so a lighter collection from the same table is always an allowed substitute.
The general shape worth remembering: a running maximum is only safe over a dimension where "less is always acceptable". Weight has that property. Item count also has it, but only if you are careful, and splitting into separate tables avoids having to be.
## The boundary that breaks a careless implementation
A left count table may be missing. If k minus c is 5 but the left half only has seventeen items, tables 0 through 17 exist, so that is fine; but if k is larger than the number of left items, the loop must stop at what exists rather than reading past it. Equally, a right collection with count already above k must be skipped entirely, and k can be 0, where only the empty collection is allowed and the answer is 0.
Items of weight 0 are still items: they consume one of the k slots even though they consume no capacity.
## Overflow
The capacity reaches 3.4 * 10^10 and the total value reaches 3.4 * 10^10, both past the 32-bit signed limit of 2147483647, so weights, values and the capacity all need 64 bits.
## Cost
2^(n/2) per half, a sort, and up to k + 1 binary searches per right collection. At n = 34 and k = 34 that is 2^17 times 18 searches, which is a few tens of millions of steps.
## Worked example
``` items (3,4) (4,5) (5,6) (2,3) (1,1) capacity 10 k = 2
left half (3,4) (4,5) table for count 0: weight 0 value 0 table for count 1: weight 3 value 4 | weight 4 value 5 -> running max 4, 5 table for count 2: weight 7 value 9
right half (5,6) (2,3) (1,1) collections include (0,0,0) (5,6,1) (2,3,1) (7,9,2) (1,1,1) (3,4,2) (6,7,2) (8,10,3)
r = (2,3,1) room 8 left counts allowed 0 and 1 count 0 -> value 0, total 3 count 1 -> heaviest <= 8 is weight 4, running max 5, total 8 r = (3,4,2) room 7 left counts allowed 0 only, total 4 r = (1,1,1) room 9 count 1 -> running max 5, total 6 r = (7,9,2) room 3 left counts allowed 0 only, total 9
answer 9 ```
### Constraints - 1 <= n <= 34 - 0 <= k <= n - 0 <= each weight <= 10^9 - 0 <= each value <= 10^9 - 0 <= capacity <= 3.4 * 10^10 - Weights, values and the capacity all pass the 32-bit signed limit when accumulated. Use a 64-bit type throughout.