0710MediumArrayDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmaskKnapsack ProblemComplete Knapsack

Cheapest Basket at the Fastener Counter

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(S * m * n) where S is the number of distinct remaining-want vectors reached, m the bundle count and n the number of kinds; S is at most the product of the wanted amounts plus one each.Space O(S * n) for the memo table plus recursion depth bounded by the total wanted.

The only thing that matters at any point is how many of each kind are still wanted, so search over that vector and memoise it. For a given vector, one option is to buy all the remaining fasteners singly, which gives an immediate baseline. Every bundle that fits inside the vector gives another option: pay its price and solve the smaller vector left behind, which also allows the same bundle again further down. Rejecting a bundle that does not fit is what enforces the no-overbuying rule. Because each bundle removes at least one fastener, the search depth is bounded by the total number wanted.

Pythonentry point: cheapest_basket

def cheapest_basket(unit, bundles, want):
    # Memoised search over the amounts still wanted. Every bundle removes at
    # least one fastener, so the search depth is bounded by the total wanted.
    n = len(unit)
    usable = [b for b in bundles if sum(b[:n]) > 0]
    memo = {}

    def solve(state):
        seen = memo.get(state)
        if seen is not None:
            return seen
        best = 0
        for i in range(n):
            best += state[i] * unit[i]
        for b in usable:
            fits = True
            for i in range(n):
                if b[i] > state[i]:
                    fits = False
                    break
            if fits:
                nxt = tuple(state[i] - b[i] for i in range(n))
                cand = b[n] + solve(nxt)
                if cand < best:
                    best = cand
        memo[state] = best
        return best

    return solve(tuple(want))

The obvious version

Fill a table over every remaining-want vector from the all-zero one upwards, taking for each the cheaper of buying everything singly and paying for any bundle that fits plus the already-computed value of what would be left. Visits the whole grid whether or not a vector is reachable.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_cheapest_basket(unit, bundles, want):
    import itertools
    n = len(unit)
    table = {}
    for state in itertools.product(*[range(w + 1) for w in want]):
        cheapest = 0
        for i in range(n):
            cheapest += state[i] * unit[i]
        for b in bundles:
            if sum(b[:n]) == 0:
                continue
            fits = True
            for i in range(n):
                if b[i] > state[i]:
                    fits = False
                    break
            if fits:
                earlier = tuple(state[i] - b[i] for i in range(n))
                cand = b[n] + table[earlier]
                if cand < cheapest:
                    cheapest = cand
        table[state] = cheapest
    return table[tuple(want)]

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in