Limited Stock Haul
Medium2-D Dynamic Programming
Problem
A delivery van can carry at most capacity kilograms. The warehouse has counts[i] identical units of product i, each weighing weights[i] kilograms and worth values[i].
You may load any number of units of product i from 0 to counts[i]. Return the maximum total value that fits in the van.
Example 1
- Input:
- weights = [2, 3], values = [3, 5], counts = [3, 1], capacity = 7
- Output:
- 11
Two units of product 0 (4 kg, value 6) plus the single unit of product 1 (3 kg, value 5).
Example 2
- Input:
- weights = [4], values = [10], counts = [5], capacity = 13
- Output:
- 30
Only three units fit.
Constraints
- 1 ≤ weights.length = values.length = counts.length ≤ 100
- 1 ≤ weights[i] ≤ 1000, 0 ≤ values[i] ≤ 1000
- 0 ≤ counts[i] ≤ 1000
- 0 ≤ capacity ≤ 2000
Hint
Show the first hint
Treating every unit as its own 0/1 item works, but how many items would that create in the worst case?
Walkthrough
How to approach it
01Clarify before coding
- Are units of the same product interchangeable? Yes, only how many you take matters.
- Can a count be 0? Yes, that product is simply unavailable.
- Must the van be full? No, at most capacity.
02Brute force
Expand every unit into its own 0/1 item (up to 100 · 1000 = 10^5 items) and run the 0/1 knapsack, or try every count per product in the DP.
Cost: O(Σcounts · capacity) = 10^5 · 2000 = 2 · 10^8 updates: too slow, and the per-product count loop is just as bad.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.