Fewest batches to ship an order
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A warehouse ships items in fixed batch sizes, listed in sizes; any size can be used any number of times.
Return the fewest batches whose sizes add up to exactly total, or -1 if no combination does. Shipping nothing takes 0 batches.
- 1 ≤ sizes.length ≤ 50
- 1 ≤ sizes[i] ≤ 10,000
- 0 ≤ total ≤ 100,000
Examples
fewestBatches([1, 3, 4], 6)returns23 + 3. Taking the largest first gives 4 + 1 + 1.fewestBatches([5, 10], 3)returns-1fewestBatches([7], 0)returns0
Hints
Hint 1 of 2
Let best[t] be the fewest batches that add up to exactly t. How does best[t] follow from best of smaller totals?
Hint 2 of 2
best[t] is 1 plus the smallest best[t - s] over every size s up to t. Start with best[0] = 0 and fill upwards.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Taking the largest batch that fits feels right and is wrong: with sizes 1, 3 and 4, a total of 6 is 3 + 3, two batches, while greedy takes 4 + 1 + 1.
Every way of shipping t ends with some last batch s, and what comes before it is a way of shipping t - s. So the fewest batches for t is one more than the fewest for t - s, minimised over every size. That is the whole recurrence.
Plain recursion asks for the same totals over and over, exponentially often. Fill an array from 0 up instead: when you reach t, every smaller total is already answered. Infinity marks totals that cannot be made, and stays Infinity through the + 1.
function fewestBatches(sizes, total) {
const best = new Array(total + 1).fill(Infinity);
best[0] = 0;
for (let t = 1; t <= total; t++)
for (const s of sizes) if (s <= t && best[t - s] + 1 < best[t]) best[t] = best[t - s] + 1;
return best[total] === Infinity ? -1 : best[total];
}Complexity. O(total × sizes) time, O(total) space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.