Unlimited Crate Restock
Problem
A shop restocks a storeroom with capacity units of free floor space. The supplier sells crate type i, which takes sizes[i] units of space and earns profits[i] when sold. Every crate type can be ordered any number of times.
Return the maximum total profit of an order whose total size is at most capacity.
Example 1
- Input:
- sizes = [2, 3, 5], profits = [5, 8, 13], capacity = 10
- Output:
- 26
Two size-5 crates give 26, as do two size-3 plus two size-2 crates (16 + 10). No combination reaches 27.
Example 2
- Input:
- sizes = [4, 6], profits = [9, 13], capacity = 3
- Output:
- 0
Not even one crate fits.
Constraints
- 1 ≤ sizes.length = profits.length ≤ 100
- 1 ≤ sizes[i] ≤ 10^4
- 0 ≤ profits[i] ≤ 10^4
- 0 ≤ capacity ≤ 10^4
Hint
Show the first hint
Compare with the take-it-or-leave-it backpack: what changes when a crate type never runs out?
Walkthrough
How to approach it
01Clarify before coding
- Is the supply of each crate type really unlimited? Yes, any count, including zero.
- Must the storeroom be completely full? No, at most capacity.
- Can a profit be zero? Yes; such crates are simply never useful.
02Brute force
Recursively try every count of every crate type: for type i choose k = 0..capacity / sizes[i] crates and recurse on the rest.
Cost: Exponential in the number of types; even with tiny sizes the count choices multiply out of control.
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.