Update: July 11 晚上
刚才看了一下别人的代码，比我的要简洁很多，首先他没有新开一个dfs函数，这代表着它不需要我的dfs函数里的start和amount两个变量；为什么，
第一，对于start，他似乎是每次都从0开始的，但这好像会多很多次判断，比如递归栈112和121（数字代表商品编号）都表示买了两个offer1和一个offer2，这就没必要了；
第二，它不需要用数组计算买了special offer的数量，因为他这么递归的：如果是成立的offer就递归，每次递归都把当前offer的价钱加上加到总价里，dfs达到最深处后Math.min比较一次再backtracking，这有点像treedepth的递归方法（每次+1 depth），免去了记录每个special offer分别买了几个；而我是用boolean作返回值，当不满足了就返回true，才开始recurse，这时候我先把数量加回来，再把needs加回来，再算钱；思路也挺清晰的其实。
if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
result = Math.min(result, shoppingOffers(price, special, needs) + offer.get(needs.size()));
}
下面是他的代码：
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int result = Integer.MAX_VALUE;
//apply each offer to the needs, and recurse
for(int i = 0; i < special.size(); i++) {
List<Integer> offer = special.get(i);
boolean invalidOffer = false;
for(int j = 0; j < needs.size(); j++) { // subtract offer items from needs
int remain = needs.get(j) - offer.get(j);
needs.set(j, remain);
if(!invalidOffer && remain < 0) invalidOffer = true; // if offer has more items than needs
}
if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
result = Math.min(result, shoppingOffers(price, special, needs) + offer.get(needs.size()));
}
for(int j = 0; j < needs.size(); j++) { // reset the needs
int remain = needs.get(j) + offer.get(j);
needs.set(j, remain);
}
}
// choose b/w offer and non offer
int nonOfferPrice = 0;
for(int i = 0; i < needs.size(); i++) {
nonOfferPrice += price.get(i) * needs.get(i);
}
return Math.min(result, nonOfferPrice);
}
July 11 早上
商店里有些是捆绑打折商品，你可以自由搭配地买，求最小价钱。
这题AC的一瞬间我叫了出来。。。是我最不擅长的递归。。虽然一遍遍调试，但是真的写出来了！！
我的思路是模仿Combination Sum那种，其实就是NP问题那种for循环+递归遍历所有可能。但是在恢复现场的时候我遇到了一些问题，因为不仅需要return true的时候恢复，找不到的时候也要恢复的。
原始代码贴在下面，后续再看看优化。
int min;
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int kinds = price.size();
if (kinds == 0) return 0;
for (int i = 0; i < kinds; i++) {
min += needs.get(i) * price.get(i);
}
dfs(0, price, special, new int[special.size()], needs);
return min;
}
private boolean dfs(int start, List<Integer> price, List<List<Integer>> special, int[] specialAmount, List<Integer> needs) {
for (int i = 0; i < needs.size(); i++) {
if (needs.get(i) < 0) {
//对比一次
return true;
}
}
for (int i = start; i < special.size(); i++) {
List<Integer> pack = special.get(i);
specialAmount[i]++;
for (int j = 0; j < needs.size(); j++) {
needs.set(j, needs.get(j) - pack.get(j));
}
if (dfs(start, price, special, specialAmount, needs)) {
specialAmount[i]--;
int total = 0;
for (int k = 0; k < needs.size(); k++) {
needs.set(k, needs.get(k) + pack.get(k));
//pack以外需要的钱
total += needs.get(k) * price.get(k);
}
//pack需要的钱
for (int m = 0; m < special.size(); m++) {
total += specialAmount[m] * special.get(m).get(pack.size() - 1);
}
min = Math.min(total, min);
} else {
specialAmount[i]--;
for (int k = 0; k < needs.size(); k++) {
needs.set(k, needs.get(k) + pack.get(k));
}
}
}
return false;
}
