C++刷LeetCode（638. 大礼包）【回溯】
题目描述：在LeetCode商店中， 有许多在售的物品。
然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。
示例 1:
输入: , [,],
输出: 14
解释:
有A和B两种物品，价格分别为￥2和￥5。
大礼包1，你可以以￥5的价格购买3A和0B。
大礼包2， 你可以以￥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了￥10购买了1A和2B（大礼包2），以及￥4购买2A。
示例 2:
输入: , [,],
输出: 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更加便宜。
说明:
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shopping-offers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
bool valid(vector<int>&store, vector<int>&needs){
for(int i = 0 ; i < store.size() - 1; i++){
if(store > needs) return false;
}
return true;
}
void dfs(vector<int>&price, vector<vector<int> >&store, vector<int>&needs, int & res, int sum){
if(sum > res) return;
int number = accumulate(needs.begin(), needs.end(), 0);
if(number == 0){//你不可以购买超出待购清单的物品，即使更便宜。
res = min(res, sum);
return;
}
bool match = false;
for(int i = 0; i < store.size(); i++){
if(valid(store, needs)){
match = true;
for(int j = 0; j < store.size() - 1; j++){
needs -= store;
}
dfs(price, store, needs, res, sum + store.back());
for(int j = 0; j < store.size() - 1; j++){
needs += store;
}
}
}
if(match == false){
for(int i = 0; i < needs.size(); i++){
sum += needs * price;
}
res = min(res, sum);
}
}
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
//采用贪心的算法，先在不超过needs数的情况下尽可能的先选组合，最后再单买
//去除组合大于单买和大于需要个数的组合数
int len1 = special.size(), len2 = special.size();
vector<vector<int> > store;
for(int i = 0; i < len1; i++){
int temp = 0;
bool flag = true;
for(int j = 0 ; j < len2 - 1; j++){
temp += special * price;
if(special > needs) flag = false;
}
if(flag && temp > special) store.push_back(special);
}
int res = INT_MAX;
dfs(price, store, needs, res, 0);
return res;
}
};
注意事项：
下面这样的输入没有办法实现，正常应该是5，而得到的结果是16。这道题应该是把这种情况剔除掉了。
price =
special = []
needs =
代码参考链接：https://leetcode-cn.com/problems/shopping-offers/solution/c-hui-su-fa-by-da-li-wang-6/ {:10_327:} {:10_275:}
页:
[1]