Leetcode之深度优先搜索&回溯专题-638. 大礼包（Shopping Offers）
深度优先搜索的解题详细介绍，点击
在LeetCode商店中， 有许多在售的物品。 然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。 现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。 每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。 任意大礼包可无限次购买。 示例 1: 输入: [2,5], [[3,0,5],[1,2,10]], [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: 输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [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更加便宜。
说明: 最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。
分析：
给定N个商品，给定M个长度为N+1的礼包，并给定长度为N的List来存储每个商品需要几个，求怎样购买价格最低。
例子看示例1.
这个问题可以转化为：
1、先求出我最多可以买几个该礼包？
2、循环 0-最大购买数量 次，即购买该礼包 0次到最大购买次数个
举个例子，A礼包我最多可以买2个，那么我DFS进入到以下几个步骤：
- 购买0个A礼包 -> 购买B礼包
- 购买1个A礼包 -> 购买B礼包
- 购买2个A礼包 -> 购买B礼包
3、循环到礼包列表的最末端后，检查有哪些商品是目前还缺的，把缺的商品，以其单价购买。
4、最后再计算总价，求出最小值。
AC代码：
class Solution {
int ans = Integer.MAX_VALUE;
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
if(price.size()==0 || price==null) return 0;
dfs(price,special,needs,0,0);
return ans;
}
public void dfs(List<Integer> price,List<List<Integer>> special,List<Integer> needs,int step,int money){
if(step>=special.size()){
for (int i = 0; i < needs.size(); i++) {
money += needs.get(i)*price.get(i);
}
ans = Math.min(ans, money);
return;
}
List<Integer> pack = special.get(step);
int value = pack.get(pack.size()-1);
int maxNum = Integer.MAX_VALUE;
for(int i=0;i<needs.size();i++){
if(pack.get(i)!=0){
int temp = needs.get(i)/pack.get(i);
maxNum = Math.min(maxNum, temp);
}
}
for(int i=0;i<=maxNum;i++){
List<Integer> temp = new ArrayList<>(needs);
for(int j=0;j<needs.size();j++){
needs.set(j, needs.get(j)-i*pack.get(j));
}
int cost = i*value;
if(money+cost<ans){
dfs(price,special,needs,step+1,money+cost);
}
needs = new ArrayList<>(temp);
}
}
}