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) ?

I think in general if the length of needs array is large, and the values (quantities of each product) is small, we won't benefit from memoization (hashing the large array will be bottleneck), however if needs array size is small and product quantity values are large, then we may benefit from memoization.

Can anyone explain what if the length of special is smaller than the length of needs?
For example:
kinds of items: [2,5]
special offer: [[3,0,5],[1,2,10]]
needs: [3,2]the needs is [3,2], however, the special offer is [3,5] which means $5 you can get 3 A items and 0 B items.
The following code will fail because for j, it misread the second number in special offer list as item instead of the amount you need to pay.
if (j == needs.size())
res = Math.min(res, s.get(j) + shopping(price, special, clone, map));
s.get(j) will be out of boundary.