class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
//商品单个购买,不选择礼包
int minPrice = 0;
for (int i = 0; i < needs.size(); ++i) {
minPrice += needs[i]*price[i];
}
//选择礼包
for(int i = 0; i < needs.size(); i++)
{
//每次递归一个礼包
if(checkValid(special[i], needs))
{
vector<int> remainNeeds;
for(int j = 0; j < needs.size(); j ++)
{
//剩余需求商品
remainNeeds.push_back(needs[j] - special[i][j]);
}
//当前花费=递归下一层花费+本次礼包花费
int tempPrice = shoppingOffers(price, special, remainNeeds) + special[i][needs.size()];
//比较当前花费与直接购买商品花费对比,得到当前递归层最低消费
minPrice = min(minPrice, tempPrice);
}
}
return minPrice;
}
bool checkValid(vector<int>& special, vector<int>& needs)
{
for(int i = 0; i < needs.size(); i++)
{
if(special[i] > needs[i])
{
return false;
}
}
return true;
}
};
水题,递归。
直接给出代码。
转载于:https://www.cnblogs.com/CGJobs/p/9123148.html