Cookie Box Order
A bakery never sells loose cookies. They only come in boxes of a few fixed sizes, say 1, 6 and 10, and the shop has plenty of each. A school orders exactly 12 cookies for a class party: no more, no fewer.
Every box needs a ribbon and a label, so the baker wants to fill the order with as few boxes as possible.
Your task
Write fewestBoxes(sizes, count). sizes lists the box sizes; you may use any size as many times as you like. Return the smallest number of boxes whose sizes add up to exactly count.
If no mix of boxes adds up to exactly count, return -1. An order of 0 cookies needs 0 boxes.
fewestBoxes(sizes: int[], count: int) → int
Examples
sizes = [1, 6, 10] count = 12
2
Two boxes of 6 make 12. Grabbing the biggest box first gives 10 + 1 + 1, which is 3 boxes. Biggest-first is not always best.
sizes = [4, 9] count = 14
-1
With no 9-box you would need 14 / 4, which is not whole. With one 9-box, 5 is left, which 4s cannot make. Two 9-boxes are already too many. So 14 is impossible.
Constraints
- 1 ≤ sizes.length ≤ 12
- 1 ≤ sizes[i] ≤ 1,000, all sizes different
- 0 ≤ count ≤ 10,000
Start with brute force
Recursively try every box as the next one until you hit the exact count or overshoot. The number of sequences explodes: with sizes 1, 2 and 5 and a count of 100 there are far more than a billion of them, and the same remainders like "40 cookies left" are solved again and again.
The greedy shortcut, always taking the biggest box that fits, is fast but wrong for sizes like [1, 6, 10].
Hints
0 of 4 shown- Hint 1
In the first example, the order of 12 must include some last box. If that last box is a 6, how many cookies did the boxes before it hold?
- Hint 2
If the last box has size
s, the rest is the best way to packcount - scookies. Try every size as the last box and keep the cheapest:fewest(c) = 1 + min over s of fewest(c - s). - Hint 3
Many orders share the same smaller amounts. Solve them once each: build an array where
best[c]is the fewest boxes for exactlyccookies, for everycfrom 0 up tocount. - Hint 4
Set
best[0] = 0and every other entry to infinity (meaning "impossible so far"). For eachcfrom 1 up, look at each sizes ≤ cand setbest[c] = min(best[c], best[c - s] + 1). At the end, infinity means -1.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Any packing has a last box. If its size is s, the other boxes must be the best packing of c - s. So the best for c is 1 plus the smallest best[c - s] over all sizes. Fill best from 0 upward so the smaller amounts are always ready.
Trace sizes [1, 6, 10], count 12. Only the interesting entries are shown:
best[0] = 0.best[1]tobest[5]can only use 1-boxes: 1, 2, 3, 4, 5.best[6]: last box 1 gives best[5] + 1 = 6; last box 6 gives best[0] + 1 = 1. So 1.best[10]: last box 10 gives best[0] + 1 = 1.best[11]: last box 1 gives best[10] + 1 = 2. (Last box 6 gives best[5] + 1 = 6.)best[12]: last box 1 gives best[11] + 1 = 3; last box 6 gives best[6] + 1 = 2; last box 10 gives best[2] + 1 = 3. So 2.
The table compares every option at each amount, which is exactly what greedy skips.
function fewestBoxes(sizes, count) {
// best[c] = fewest boxes for exactly c cookies (Infinity = impossible)
const best = new Array(count + 1).fill(Infinity);
best[0] = 0;
for (let c = 1; c <= count; c++) {
for (const s of sizes) {
// try s as the last box
if (s <= c && best[c - s] + 1 < best[c]) best[c] = best[c - s] + 1;
}
}
return best[count] === Infinity ? -1 : best[count];
}def fewest_boxes(sizes, count):
INF = float("inf")
# best[c] = fewest boxes for exactly c cookies (INF = impossible)
best = [0] + [INF] * count
for c in range(1, count + 1):
for s in sizes:
# try s as the last box
if s <= c and best[c - s] + 1 < best[c]:
best[c] = best[c - s] + 1
return -1 if best[count] == INF else best[count]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.