Show problems as
Classic problem #638MediumArrayDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmaskKnapsack ProblemComplete Knapsack

Shopping Offers

Real-world version: Cheapest Basket at the Fastener Counter
Tracked in this browser only
Read Shopping Offers on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A hardware counter sells several kinds of fastener. unit[i] is the price of one fastener of kind i, bought on its own.

The counter also lists pre-packed bundles. bundles[k] holds one more number than there are kinds: bundles[k][i] is how many fasteners of kind i the bundle contains, and the last number is what the bundle costs. Every bundle contains at least one fastener, and a bundle may be bought as many times as you like, or not at all.

You must walk out holding exactly want[i] fasteners of kind i. Buying more of any kind than you want is not allowed, even when it would be cheaper, so a bundle can only be bought while every kind it contains is still wanted in at least that quantity.

Return the least you can pay.

Examples

Example 1

Input
unit = [3, 5], bundles = [[1, 2, 10], [2, 1, 9]], want = [2, 3]
Output
18

Buying the first bundle once costs 10 and supplies one fastener of the first kind and two of the second. One of each kind is still wanted, bought singly for 3 and 5. The basket holds exactly two and three fasteners and cost 18.

Example 2

Input
unit = [10, 10], bundles = [[2, 2, 5]], want = [1, 1]
Output
20

The only bundle holds two of each kind, but only one of each is wanted, so buying it would overshoot and is not allowed. One fastener of each kind bought singly costs 20.

Example 3

Input
unit = [10, 10, 10], bundles = [[2, 1, 0, 15], [0, 1, 2, 15]], want = [2, 2, 2]
Output
30

Buying each bundle once costs 30 and supplies two, two and two fasteners of the three kinds, exactly what is wanted, with nothing left to buy singly.

Constraints

  • 1 <= unit.length <= 6
  • unit.length == want.length
  • 0 <= unit[i] <= 10
  • 0 <= want[i] <= 10
  • 1 <= bundles.length <= 100
  • 2 <= bundles[i].length <= 7
  • Each bundles[i] has exactly one more entry than unit, the extra one being the bundle price.
  • 0 <= bundles[i][j] <= 50
  • Every bundle contains at least one fastener.

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.

Python
def cheapest_basket(unit: list[int], bundles: list[list[int]], want: list[int]) -> int:
Java
public int cheapestBasket(List<Integer> unit, List<List<Integer>> bundles, List<Integer> want)

More on the same topics