Fewest batches to ship an order

MediumAbout 30 minProblem 1 of 2 in Dynamic programmingDraft

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

  1. fewestBatches([1, 3, 4], 6)returns 23 + 3. Taking the largest first gives 4 + 1 + 1.
  2. fewestBatches([5, 10], 3)returns -1
  3. fewestBatches([7], 0)returns 0

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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open