Exact Shelf Fill
Medium · dynamic programming
A carpenter is lining a bookcase with a single shelf that is exactly width centimetres wide. The workshop has a pile of offcut planks, and the list planks holds the length of every plank in centimetres.
The shelf is filled by laying planks side by side. Pick some of the planks, each plank at most once, whose lengths add up to exactly width.
Return the fewest planks that can fill the shelf exactly. If no choice of planks adds up to width, return -1.
Examples
Example 1
Input: planks = [4, 3, 2, 6, 1], width = 7
Output: 2
4 + 3 and 6 + 1 both fill the shelf with two planks, and no single plank is 7 long.
Example 2
Input: planks = [5, 5], width = 10
Output: 2
Both planks are needed.
Example 3
Input: planks = [4, 6], width = 5
Output: -1
No choice of planks adds up to 5.
Constraints
- 1 <= len(planks) <= 60
- 1 <= planks[i] <= 100
- 1 <= width <= 600