C++刷LeetCode（638. 大礼包）【回溯】

糖逗

题目描述：

1. 在LeetCode商店中， 有许多在售的物品。
   
2. 
   
3. 然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
   
4. 
   
5. 现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
   
6. 
   
7. 每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
   
8. 
   
9. 任意大礼包可无限次购买。
   
10. 
    
11. 示例 1:
    
12. 
    
13. 输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
    
14. 输出: 14
    
15. 解释:
    
16. 有A和B两种物品，价格分别为￥2和￥5。
    
17. 大礼包1，你可以以￥5的价格购买3A和0B。
    
18. 大礼包2， 你可以以￥10的价格购买1A和2B。
    
19. 你需要购买3个A和2个B， 所以你付了￥10购买了1A和2B（大礼包2），以及￥4购买2A。
    
20. 示例 2:
    
21. 
    
22. 输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
    
23. 输出: 11
    
24. 解释:
    
25. A，B，C的价格分别为￥2，￥3，￥4.
    
26. 你可以用￥4购买1A和1B，也可以用￥9购买2A，2B和1C。
    
27. 你需要买1A，2B和1C，所以你付了￥4买了1A和1B（大礼包1），以及￥3购买1B， ￥4购买1C。
    
28. 你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
    
29. 说明:
    
30. 
    
31. 最多6种物品， 100种大礼包。
    
32. 每种物品，你最多只需要购买6个。
    
33. 你不可以购买超出待购清单的物品，即使更便宜。
    
34. 
    
35. 来源：力扣（LeetCode）
    
36. 链接：https://leetcode-cn.com/problems/shopping-offers
    
37. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool valid(vector<int>&store, vector<int>&needs){
   
4.         for(int i = 0 ; i < store.size() - 1; i++){
   
5.             if(store[i] > needs[i]) return false;
   
6.         }
   
7.         return true;
   
8.     }
   
9.     void dfs(vector<int>&price, vector<vector<int> >&store, vector<int>&needs, int & res, int sum){
   
10.         if(sum > res) return;
    
11.         int number = accumulate(needs.begin(), needs.end(), 0);
    
12.         if(number == 0){//你不可以购买超出待购清单的物品，即使更便宜。
    
13.             res = min(res, sum);
    
14.             return;
    
15.         }
    
16.         bool match = false;
    
17.         for(int i = 0; i < store.size(); i++){
    
18.             if(valid(store[i], needs)){
    
19.                 match = true;
    
20.                 for(int j = 0; j < store[0].size() - 1; j++){
    
21.                     needs[j] -= store[i][j];
    
22.                 }
    
23.                 dfs(price, store, needs, res, sum + store[i].back());
    
24.                 for(int j = 0; j < store[0].size() - 1; j++){
    
25.                     needs[j] += store[i][j];
    
26.                 }
    
27.             }
    
28.         }
    
29.         if(match == false){
    
30.             for(int i = 0; i < needs.size(); i++){
    
31.                 sum += needs[i] * price[i];
    
32.             }
    
33.             res = min(res, sum);
    
34.         }
    
35.     }
    
36.     int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
    
37.         //采用贪心的算法，先在不超过needs数的情况下尽可能的先选组合，最后再单买
    
38.         //去除组合大于单买和大于需要个数的组合数
    
39.         int len1 = special.size(), len2 = special[0].size();
    
40.         vector<vector<int> > store;
    
41.         for(int i = 0; i < len1; i++){
    
42.             int temp = 0;
    
43.             bool flag = true;
    
44.             for(int j = 0 ; j < len2 - 1; j++){
    
45.                 temp += special[i][j] * price[j];
    
46.                 if(special[i][j] > needs[j]) flag = false;
    
47.             }
    
48.             if(flag && temp > special[i][len2-1]) store.push_back(special[i]);
    
49.         }
    
50.         int res = INT_MAX;
    
51.         dfs(price, store, needs, res, 0);
    
52.         return res;
    
53. 
    
54.     }
    
55. };

复制代码

注意事项：

1. 下面这样的输入没有办法实现，正常应该是5，而得到的结果是16。这道题应该是把这种情况剔除掉了。
   
2. 
   
3. price = [2,5]
   
4. special = [[4,2,5]]
   
5. needs = [3,2]

复制代码

代码参考链接：https://leetcode-cn.com/problems ... fa-by-da-li-wang-6/

糖逗

小甲鱼的铁粉