Problem

In LeetCode Store, there are n items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given an integer array price where price[i] is the price of the iᵗʰ item, and an integer array needs where needs[i] is the number of pieces of the iᵗʰ item you want to buy.

You are also given an array special where special[i] is of size n + 1 where special[i][j] is the number of pieces of the jᵗʰ item in the iᵗʰ offer and special[i][n] (i.e., the last integer in the array) is the price of the iᵗʰ offer.

Return the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. You are not allowed to buy more items than you want, even if that would lower the overall price. You could use any of the special offers as many times as you want.

https://leetcode.cn/problems/shopping-offers/

Example 1:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14
Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
Output: 11
Explanation: The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.

Constraints:

  • n == price.length == needs.length
  • 1 <= n <= 6
  • 0 <= price[i], needs[i] <= 10
  • 1 <= special.length <= 100
  • special[i].length == n + 1
  • 0 <= special[i][j] <= 50
  • The input is generated that at least one of special[i][j] is non-zero for 0 <= j <= n - 1.

Test Cases

1
2
class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pytest

from solution import Solution


@pytest.mark.parametrize('price, special, needs, expected', [
    ([2,5], [[3,0,5],[1,2,10]], [3,2], 14),
    ([2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1], 11),

    (
        [4,7,9,9,3,2],
        [[0,0,4,6,2,0,22],[1,4,3,5,5,3,10],[4,5,6,3,4,1,29],[0,3,2,2,4,2,4],[4,6,3,4,4,6,21],[5,6,3,6,3,4,23],[6,1,3,4,6,2,9],[3,3,6,1,5,1,16],[0,3,6,4,0,2,5],[5,1,2,3,5,5,7],[0,1,1,6,2,4,24],[1,5,2,2,6,1,3],[4,2,2,4,3,1,8],[3,1,0,6,1,2,30],[4,6,1,4,0,0,2],[0,4,5,6,2,5,1],[2,6,0,6,6,2,21],[2,1,3,4,0,2,2],[6,4,4,4,1,3,24],[6,3,1,6,5,5,12],[1,3,2,1,3,2,32],[2,2,0,3,1,2,16],[2,4,3,6,6,5,26],[1,6,3,5,0,4,2],[6,2,1,5,6,2,9],[0,4,2,2,5,3,3],[6,3,3,6,0,5,9],[4,3,2,5,3,3,29],[1,6,0,0,1,6,31],[5,6,0,5,4,3,31],[0,4,2,6,0,6,28],[5,4,3,2,5,3,32],[6,5,1,1,4,6,18],[3,3,3,2,3,3,2],[5,6,2,5,3,3,7],[1,2,6,4,4,0,18],[0,4,4,0,0,3,18],[4,2,0,0,3,3,19],[6,0,4,4,4,6,15],[6,2,3,0,2,2,4],[4,1,1,5,5,5,14],[3,6,4,0,6,2,27],[2,4,6,2,2,3,24],[6,0,5,3,1,6,7],[3,1,5,1,2,6,28],[5,2,2,1,1,4,25],[5,6,5,0,3,4,19],[3,5,3,3,5,1,31],[6,0,1,1,6,4,14],[0,3,4,3,3,4,10],[4,1,2,2,0,0,27],[2,2,1,3,5,2,24],[2,3,2,6,1,1,21],[6,6,5,6,2,2,12],[6,6,3,1,0,6,28],[6,4,1,6,5,0,8],[3,3,0,5,4,2,7],[4,3,3,3,0,2,25],[1,2,0,5,2,4,8],[0,1,6,6,5,5,27],[3,6,4,5,2,2,4],[4,4,6,1,5,3,30],[4,3,4,5,5,5,19],[0,0,0,6,1,0,27],[6,5,0,1,2,4,10],[2,6,0,0,1,0,13],[4,1,6,1,4,1,24],[2,4,0,1,4,1,25],[5,1,3,3,4,1,8],[5,5,1,0,2,1,25],[1,6,2,4,0,6,27],[4,0,3,0,5,3,30],[2,4,6,6,3,2,4],[6,4,2,2,0,3,27],[1,2,1,2,2,1,2],[2,0,3,0,5,4,4],[3,5,4,4,1,1,25],[2,1,1,6,3,3,28],[4,4,4,3,6,3,21],[1,4,1,4,2,2,27],[0,6,0,2,2,2,33],[3,3,5,6,4,6,9],[1,0,0,3,4,2,11],[1,3,0,3,0,1,16],[2,3,0,0,0,5,1],[3,5,6,4,1,4,3],[3,1,0,2,6,0,19],[3,0,0,5,3,1,6],[1,0,4,1,2,2,18],[0,0,4,3,5,1,31],[4,4,2,5,5,2,2],[5,0,2,6,5,3,4],[6,2,1,0,2,3,11],[4,5,1,5,3,3,23],[6,2,5,1,6,6,4],[5,6,6,1,5,6,6],[3,2,6,1,4,5,19],[0,2,6,2,5,0,26],[0,1,3,6,3,6,18],[3,5,4,6,5,3,6]],
        [6,6,6,6,6,6],
        22
    )
])
class Test:
    def test_solution(self, price, special, needs, expected):
        sol = Solution()
        assert sol.shoppingOffers(price, special, needs) == expected

Thoughts

相当于 322. Coin Change 的进阶版，从一个币种升级成同时处理 n 个币种，目标从硬币数量最少升级为带权总和最小，除此之外没有其他本质区别。

对于任意一个需求集 (i₁, i₂, ..., iₙ)，要么按照每个物品的单价直接购买，要么先买下某个 special offer 然后再看剩下的部分怎么买。

同样可以事先过滤掉完全没用的 offer，比如比需要的物品种类或数量多，或者价格没有直接购买便宜。

虽然一般动态规划问题可以循环遍历所有的子问题，但现在这种有好几种物品需要购买的场景中，遍历全部需求量的组合就太低效，会有大量的计算浪费掉。所以直接用递归实现，用哈希表或者 Python 自带的缓存功能避免重复计算。

记 k 为 special offers 的数量，m 是 needs 中的最大值，时间复杂度为 O(mⁿ * k * n)，空间复杂度为 O(mⁿ * n)。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def shoppingOffers(self, price: list[int], special: list[list[int]], needs: list[int]) -> int:
        good = lambda o: all(a >= b for a, b in zip(needs, o)) and sum(p * c for p, c in zip(price, o)) > o[-1]
        offers = tuple(filter(good, special)) # Useless special offer removed.
        cache: dict[tuple[int], int] = {} # Or leverage functools.cache or functools.lru_cache.
        cache[(0,) * len(price)] = 0

        def min_amt(need: tuple[int]):
            if need in cache:
                return cache[need]

            amt = sum(p * c for p, c in zip(price, need)) # Direct buy.
            for offer in offers:
                remain = tuple(a - b for a, b in zip(need, offer))
                if any(r < 0 for r in remain):
                    continue
                amt = min(amt, offer[-1] + min_amt(remain))

            cache[need] = amt
            return amt

        return min_amt(tuple(needs))
medium
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~