class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
}
};
638. 大礼包
在 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.lengthn == needs.length1 <= n <= 60 <= price[i] <= 100 <= needs[i] <= 101 <= special.length <= 100special[i].length == n + 10 <= special[i][j] <= 50原站题解
cpp 解法, 执行用时: 3 ms, 内存消耗: 14 MB, 提交时间: 2024-11-03 17:42:03
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
const int bits = 4;
int n = needs.size();
unordered_map<int, int> f;
int mask = 0;
for (int i = 0; i < n; ++i) {
mask |= needs[i] << (i * bits);
}
function<int(int)> dfs = [&](int cur) {
if (f.contains(cur)) {
return f[cur];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += price[i] * ((cur >> (i * bits)) & 0xf);
}
for (const auto& offer : special) {
int nxt = cur;
bool ok = true;
for (int j = 0; j < n; ++j) {
if (((cur >> (j * bits)) & 0xf) < offer[j]) {
ok = false;
break;
}
nxt -= offer[j] << (j * bits);
}
if (ok) {
ans = min(ans, offer[n] + dfs(nxt));
}
}
f[cur] = ans;
return ans;
};
return dfs(mask);
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 41.2 MB, 提交时间: 2024-11-03 17:41:50
class Solution {
private final int bits = 4;
private int n;
private List<Integer> price;
private List<List<Integer>> special;
private Map<Integer, Integer> f = new HashMap<>();
public int shoppingOffers(
List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
n = needs.size();
this.price = price;
this.special = special;
int mask = 0;
for (int i = 0; i < n; ++i) {
mask |= needs.get(i) << (i * bits);
}
return dfs(mask);
}
private int dfs(int cur) {
if (f.containsKey(cur)) {
return f.get(cur);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += price.get(i) * (cur >> (i * bits) & 0xf);
}
for (List<Integer> offer : special) {
int nxt = cur;
boolean ok = true;
for (int j = 0; j < n; ++j) {
if ((cur >> (j * bits) & 0xf) < offer.get(j)) {
ok = false;
break;
}
nxt -= offer.get(j) << (j * bits);
}
if (ok) {
ans = Math.min(ans, offer.get(n) + dfs(nxt));
}
}
f.put(cur, ans);
return ans;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.7 MB, 提交时间: 2022-11-28 14:38:59
func shoppingOffers(price []int, special [][]int, needs []int) int {
n := len(price)
// 过滤不需要计算的大礼包，只保留需要计算的大礼包
filterSpecial := [][]int{}
for _, s := range special {
totalCount, totalPrice := 0, 0
for i, c := range s[:n] {
totalCount += c
totalPrice += c * price[i]
}
if totalCount > 0 && totalPrice > s[n] {
filterSpecial = append(filterSpecial, s)
}
}
// 记忆化搜索计算满足购物清单所需花费的最低价格
dp := map[string]int{}
var dfs func([]byte) int
dfs = func(curNeeds []byte) (minPrice int) {
if res, has := dp[string(curNeeds)]; has {
return res
}
for i, p := range price {
minPrice += int(curNeeds[i]) * p // 不购买任何大礼包，原价购买购物清单中的所有物品
}
nextNeeds := make([]byte, n)
outer:
for _, s := range filterSpecial {
for i, need := range curNeeds {
if need < byte(s[i]) { // 不能购买超出购物清单指定数量的物品
continue outer
}
nextNeeds[i] = need - byte(s[i])
}
minPrice = min(minPrice, dfs(nextNeeds)+s[n])
}
dp[string(curNeeds)] = minPrice
return
}
curNeeds := make([]byte, n)
for i, need := range needs {
curNeeds[i] = byte(need)
}
return dfs(curNeeds)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
javascript 解法, 执行用时: 120 ms, 内存消耗: 65.1 MB, 提交时间: 2022-11-28 14:38:39
/**
* @param {number[]} price
* @param {number[][]} special
* @param {number[]} needs
* @return {number}
*/
var shoppingOffers = function(price, special, needs) {
const memo = new Map();
// 记忆化搜索计算满足购物清单所需花费的最低价格
const dfs = (price, special, curNeeds, filterSpecial, n) => {
if (!memo.has(curNeeds)) {
let minPrice = 0;
for (let i = 0; i < n; ++i) {
minPrice += curNeeds[i] * price[i]; // 不购买任何大礼包，原价购买购物清单中的所有物品
}
for (const curSpecial of filterSpecial) {
const specialPrice = curSpecial[n];
const nxtNeeds = [];
for (let i = 0; i < n; ++i) {
if (curSpecial[i] > curNeeds[i]) { // 不能购买超出购物清单指定数量的物品
break;
}
nxtNeeds.push(curNeeds[i] - curSpecial[i]);
}
if (nxtNeeds.length === n) { // 大礼包可以购买
minPrice = Math.min(minPrice, dfs(price, special, nxtNeeds, filterSpecial, n) + specialPrice);
}
}
memo.set(curNeeds, minPrice);
}
return memo.get(curNeeds);
}
const n = price.length;
// 过滤不需要计算的大礼包，只保留需要计算的大礼包
const filterSpecial = [];
for (const sp of special) {
let totalCount = 0, totalPrice = 0;
for (let i = 0; i < n; ++i) {
totalCount += sp[i];
totalPrice += sp[i] * price[i];
}
if (totalCount > 0 && totalPrice > sp[n]) {
filterSpecial.push(sp);
}
}
return dfs(price, special, needs, filterSpecial, n);
};
python3 解法, 执行用时: 60 ms, 内存消耗: 15 MB, 提交时间: 2022-11-28 14:38:22
from functools import lru_cache
class Solution:
def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
n = len(price)
# 过滤不需要计算的大礼包，只保留需要计算的大礼包
filter_special = []
for sp in special:
if sum(sp[i] for i in range(n)) > 0 and sum(sp[i] * price[i] for i in range(n)) > sp[-1]:
filter_special.append(sp)
# 记忆化搜索计算满足购物清单所需花费的最低价格
@lru_cache(None)
def dfs(cur_needs):
# 不购买任何大礼包，原价购买购物清单中的所有物品
min_price = sum(need * price[i] for i, need in enumerate(cur_needs))
for cur_special in filter_special:
special_price = cur_special[-1]
nxt_needs = []
for i in range(n):
if cur_special[i] > cur_needs[i]: # 不能购买超出购物清单指定数量的物品
break
nxt_needs.append(cur_needs[i] - cur_special[i])
if len(nxt_needs) == n: # 大礼包可以购买
min_price = min(min_price, dfs(tuple(nxt_needs)) + special_price)
return min_price
return dfs(tuple(needs))