502. The Bag With Equal Weights
Every item weighs the SAME amount w. Each has its own value and may be used at most
once. The bag holds at most C total weight. Print the largest total value.
values 5 1 9 3, w = 2, C = 5 -> 14 two items fit: 9 + 5
## Read the constraints first
n reaches 2 * 10^5 and C reaches 10^9. A knapsack table indexed by capacity has
10^9 entries, so the standard approach is not available.
Whenever the standard approach is impossible, the structure of the instance is the thing to look at, and here it is unusual: the weights are all equal.
## What equal weights change
If every item weighs w, then the only thing the capacity decides is HOW MANY items may
be taken:
k = min( C / w rounded down, n )
Which items is then unconstrained. Any k of them fit, so take the k most valuable.
sort the values descending
answer = sum of the first k
The knapsack disappears. There is no interaction left between items, because the only resource is a count and every item consumes exactly one unit of it.
## Why this is the point rather than a trick
A DP is needed when a choice constrains later choices in a way that depends on WHICH choice was made. Equal weights remove that: taking item A rather than item B leaves exactly the same capacity behind. With no interaction there is nothing to tabulate, and a sort is the whole algorithm.
That test, "does the choice change what is available later, or only how much", is the one worth carrying to the next problem.
## Boundaries
values 7, w = 3, C = 2 answers 0. Nothing fits, since one item needs 3 and only 2 is
available. And C = 3 with the same input answers 7.
values 4 4 4 4, w = 2, C = 100 answers 16. The capacity allows 50 items and only 4
exist, which is why k is clamped at n.
values 9 8, w = 1000000000, C = 1000000000 answers 9. Exactly one item fits and it must
be the better one, and it is also the case where an unclamped table would be attempted.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Values reach 10^6 over 2 * 10^5 items, so the total needs 64 bits.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ w ≤ 1000000000` - `0 ≤ C ≤ 1000000000` - `1 ≤ value ≤ 1000000`
Input
The first line contains three integers n, w and C.
The second line contains n space-separated values.
Output
Print the largest total value that fits in the bag.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.