638.大礼包

链接：638.大礼包
难度：Medium
标签：位运算、记忆化搜索、数组、动态规划、回溯、状态压缩
简介：返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

题解 1 - typescript

• 编辑时间：2021-10-24
• 执行用时：76ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：dfs。

function shoppingOffers(price: number[], special: number[][], needs: number[]): number {
  const n = price.length;
  special = special
    .filter(item => {
      let sum = 0;
      for (let i = 0; i < n; i++) sum += item[i] * price[i];
      return sum > item[n];
    })
    .sort((a, b) => a[n] - b[n]);
  let ans = Infinity;
  dfs(needs);
  return ans;
  function dfs(needs: number[], cost = 0) {
    if (needs.every(v => v === 0)) {
      ans = Math.min(cost, ans);
      return;
    }
    const list = special.filter((item: number[]) =>
      item.every((v, i) => (i === n ? true : v <= needs[i]))
    );
    if (list.length === 0) {
      dfs(
        [0],
        needs.reduce((total, v, i) => price[i] * v + total, cost)
      );
    } else {
      list.forEach(item => {
        dfs(
          needs.map((v, i) => v - item[i]),
          item[n] + cost
        );
      });
    }
  }
}

题解 2 - undefined

• 编辑时间：2024-11-03
• 执行用时：67ms
• 内存消耗：19.94MB
• 编程语言：undefined
• 解法介绍：记忆化搜索。

def to_list(num: int, n: int) -> List[int]:
    res = []
    for i in range(n):
        res.append(num % 100)
        num //= 100
    res.reverse()
    return res
def to_num(needs: List[int]) -> int:
    res = 0
    for need in needs:
        res = res * 100 + need
    return res
class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        n = len(price)
        @cache
        def dfs(idx: int, need: int) -> int:
            needs = to_list(need, n)
            if idx == len(special): return sum(price[i] * needs[i] for i in range(n))
            res = inf
            for cnt in range(0x7fffffff):
                next_needs = [v for v in needs]
                f = True
                for i in range(n):
                    if special[idx][i] * cnt > next_needs[i]:
                        f = False
                        break
                    next_needs[i] -= special[idx][i] * cnt
                if not f: break
                res = min(res, dfs(idx + 1, to_num(next_needs)) + special[idx][-1] * cnt)
            return res
        return dfs(0, to_num(needs))