Maximum Number of Items From Sale I
Real-world version: Most Units Bought From the Bundle SaleThe statement here is our own: the same inputs, outputs and technique.
A sale lists its lines as items, where items[i] is [factor, price].
Line i is sold only as a whole bundle: taking it means buying exactly factor units at price each, so the bundle costs factor times price and yields factor units. A line may be taken once or left alone.
With budget to spend, return the greatest number of units that can be bought.
Examples
Example 1
- Input
- items = [[3, 4], [7, 2], [2, 9], [5, 3]], budget = 40
- Output
- 12
The four bundles cost 12, 14, 18 and 15 and yield 3, 7, 2 and 5 units. Taking the second and fourth costs 29 and yields 12 units, and no choice inside 40 does better.
Example 2
- Input
- items = [[10, 1], [1, 10]], budget = 10
- Output
- 10
One bundle costs 10 and yields 10 units, the other costs 10 and yields 1, so the budget goes on the first.
Example 3
- Input
- items = [[1, 2]], budget = 1
- Output
- 0
The only bundle costs 2, which is over budget, so nothing can be bought.
Constraints
- 1 <= items.length <= 1000
- items[i].length == 2
- 1 <= items[i][0] <= 1500
- 1 <= items[i][1] <= 1500
- 1 <= budget <= 1500
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def maximum_sale_items(items: list[list[int]], budget: int) -> int:public int maximumSaleItems(int[][] items, int budget)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's