Fewest Items to Reach a Target
Print the fewest items whose total is AT LEAST target, or -1 if even taking
everything falls short.
3 1 4 1 5, target = 8 -> 2 5 and 4
1 1 1, target = 5 -> -1
Every problem in this topic so far has needed a table. This one does not, and telling the two situations apart is the skill being tested.
## The greedy
Sort descending and take until the total reaches the target.
if sum of everything < target: return -1
s = 0, count = 0
for v in descending order:
if s >= target: stop
s += v; count++
return count
## Why it is optimal
Suppose some selection of m items reaches the target. The m LARGEST items have a
total at least as big, because replacing any chosen item by an unchosen larger one never
lowers the total. So if any m items suffice, the largest m suffice.
Therefore the smallest m that works is found by taking items in descending order and
stopping as soon as the target is met. No comparison of alternatives is needed.
The argument turns on the objective being a COUNT with no capacity limit. Add a weight limit and the exchange fails, because the larger item may not fit, and the problem becomes a genuine knapsack.
That is the distinction worth carrying away: a greedy works here not because the numbers are nice but because the constraint structure admits an exchange.
## Why the usual knapsack answer is wrong here
Building dp[t] = fewest items totalling exactly t and reading dp[target] fails,
because the requirement is AT LEAST the target. It would also cost O(n * sum), and
sum reaches 10^14 at these bounds, so the table cannot be built at all.
Recognising that the table is impossible is often the prompt to look for an exchange argument.
## Boundaries
1 1 1 with target = 5 answers -1. The check is against the total of everything,
made BEFORE the loop, because the loop itself has no way to distinguish "ran out of
items" from "finished".
2 2 2 2 with target = 7 answers 4: every item is needed and the total overshoots to
8. Overshooting is allowed, which is what "at least" means.
1 2 3 4 with target = 1 answers 1, taking the largest item even though a smaller one
would also do. The count is what is minimised, not the total.