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);
}

Further, an offer can be used only if the number of items, of each type, required for using the offer, is lesser than or equal to the ones available in the current needsneeds : Couldn't there be a case where using certain items only make the cost cheaper ? (I mean not using all the offers, still benefitted) ?