总的思路就是记忆化搜索+动态规划,对于每个礼包我选择买或不买一个,如果买了就更新需求列表,递归的对新需求进行每个礼包的选择。
我们还可以对礼包进行预处理,排除掉不合适或者无意义的礼包,减少计算量。
注意点:本题如果用贪心的思想考虑会出问题,如例:
[6,3]
[[3,2,9],[1,2,1],[0,1,5],[2,5,9]]
[6,6]
因为按照贪心思想,当前礼包合适我们就尽可能的多买当前礼包,然后继续考虑其他,但是这样不能得到最优解,即无法证明贪心法的正确性。
编程实现参考自官方题解
class Solution
{
public:
map<vector<int>, int> memo; //用来存放不同需求列表所需最低价格
int shoppingOffers(vector<int> &price, vector<vector<int>> &special, vector<int> &needs)
{
int n = price.size();
// 过滤不需要计算的大礼包,只保留需要计算的大礼包
vector<vector<int>> filterSpecial;
for (auto &sp : special)
{
int totalCount = 0, totalPrice = 0;
for (int i = 0; i < n; ++i)
{
totalCount += sp[i];
totalPrice += sp[i] * price[i];
}
if (totalCount > 0 && totalPrice > sp[n])
{
filterSpecial.emplace_back(sp);
}
}
return dfs(price, needs, filterSpecial, n);
}
int dfs(vector<int> price, vector<int> curNeeds, vector<vector<int>> &filterSpecial, int n)
{
if (!memo.count(curNeeds)) // memo存在的意义就是避免了大量的重复计算,即当前needs算过就不需要再算了
{
int minprice = 0;
for (int i = 0; i < n; ++i) //先计算所有物品单买的总价
{
minprice += curNeeds[i] * price[i];
}
for (auto &CurSpecial : filterSpecial) //使用引用类型可以节省时间
{
vector<int> NxtNeeds;
for (int i = 0; i < n; ++i) //根据购买礼包内物品是否会超出限制,更新一个新的需求列表
{
if (CurSpecial[i] > curNeeds[i])
break;
NxtNeeds.emplace_back(curNeeds[i] - CurSpecial[i]);
}
if (NxtNeeds.size() == n) //由需求列表的商品种类判断此礼包是否可以购买
{
minprice = min(minprice, dfs(price, NxtNeeds, filterSpecial, n) + CurSpecial[n]);
//每次只考虑购买一个当前礼包,因为礼包之间存在一定的最优组合,不一定一个礼包合适到要买尽可能最多
/*如输入样例[6,3]
[[3,2,9],[1,2,1],[0,1,5],[2,5,9]]
[6,6]
对于前两个优惠礼包是要组合搭配的*/
}
}
memo[curNeeds] = minprice;
}
return memo[curNeeds];
}
};