跳至主要內容

638. 大礼包

638. 大礼包

🟠   🔖  位运算 记忆化搜索 数组 动态规划 回溯 状态压缩  🔗 力扣open in new window LeetCodeopen in new window

题目

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 ith item, and an integer array needs where needs[i] is the number of pieces of the ith 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 jth item in the ith offer and special[i][n] (i.e., the last integer in the array) is the price of the ith 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.

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.

题目大意

在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

示例 1：

输入： price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]

输出： 14

解释： 有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。

大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。

大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。

需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。

示例 2：

输入： price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]

输出： 11

解释： A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。

可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。

需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。

不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。

提示：

  • 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
  • 生成的输入对于 0 <= j <= n - 1 至少有一个 special[i][j] 非零。

解题思路

这个问题的本质是 在购买商品的过程中，选择最优的购买方式，使得总价格最低。可以使用 递归 + 记忆化搜索 来优化计算过程。

  1. 递归定义：

    • 设 shopping(needs) 计算当前 needs 状态下的最低价格。
    • 计算不使用特价 special 时的总价，即 needs[i] * price[i] 之和。
    • 尝试使用特价套餐 special，如果满足条件（即所有商品的数量不变成负数），则递归计算剩余 needs 的最低价格，并取最优解。

  2. 剪枝优化：

    • 特价套餐无效剪枝：如果套餐价格大于单独购买的价格，则直接忽略这个套餐。
    • 记忆化搜索：使用 map 记录已经计算过的 needs 结果，避免重复计算。

  3. 终止条件：

    • 当 needs 为空或所有商品都购买完成时，返回 0。

复杂度分析

  • 时间复杂度：O(m^n)，其中 m 是特价套餐的数量，n 是商品种类数。最坏情况下，每种商品都可以选择多种不同的购买方式。
  • 空间复杂度：O(m * n)，用于存储记忆化搜索的 map。

代码

/**
 * @param {number[]} price
 * @param {number[][]} special
 * @param {number[]} needs
 * @return {number}
 */
var shoppingOffers = function (price, special, needs) {
	const n = price.length;
	const memo = new Map();

	const shopping = (needs) => {
		const key = needs.join(',');
		if (memo.has(key)) return memo.get(key);

		// 计算直接购买的总价格（不使用特价）
		let minPrice = needs.reduce((acc, cur, i) => acc + cur * price[i], 0);

		// 遍历所有特价套餐，尝试使用
		for (let offer of special) {
			let newNeeds = [...needs];
			let i = 0;
			for (; i < n; i++) {
				let remain = needs[i] - offer[i];
				if (remain < 0) break; // 不能购买该特价套餐
				newNeeds[i] = remain;
			}
			if (i === n) {
				// 计算使用该套餐后的最小价格
				minPrice = Math.min(minPrice, offer[n] + shopping(newNeeds));
			}
		}

		memo.set(key, minPrice);
		return minPrice;
	};

	return shopping(needs);
};
Copyright © 2025 2xiao