Shopping Offers


@aqin Math.min(
special.get(i).get(j) + shopping(price, special, clone, i)
, shopping(price, special, needs, i + 1));
First part is considering ith offer and still callingshopping
for i. That means ith offer can be considered again.


@aqin From the recursion, it shows that a special offer can be used multiple times: in
shopping(price, special, needs', i) + offer_price_i
, theith
special offer is NOT excluded from subsequent choices though it has already been chosen once.

I think the following code is more clear and shallow recursion depth than sample code
int search(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int id){
if (id == special.size()){
return IntStream.range(0, needs.size()).map(i> price.get(i) * needs.get(i)).sum();
}
int cost = Integer.MAX_VALUE;
List<Integer> offer = special.get(id);
boolean isOk = true;
for (int i = 0;isOk; i++){
for (int j = 0; j < needs.size(); j++){
if (needs.get(j) < i * offer.get(j)){
isOk = false;
}
needs.set(j, needs.get(j)  i * offer.get(j));
}
if (isOk){
cost = Math.min(cost, offer.get(offer.size()  1) * i + fuck(price, special, needs, id + 1));
}
for (int j = 0; j < needs.size(); j++){
needs.set(j, needs.get(j) + i * offer.get(j));
}
}
return cost;
}
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
return search(price, special, needs, 0);
}