# Shopping Offers

• "You could use any of special offers as many times as you want." This sentence makes me think that we could use special offer such "A" multi-times.
But from the solution, it seems we could only use each special offer once?

• @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 calling `shopping` for i. That means ith offer can be considered again.

• There is another way using dynamic programming. In fact, it's a Complete knapsack problem in high dimension.

• Could you please explain why time complexity is 2^N?
The problem specifies that for each special offer, we can take as many times as we want.

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

• i think we can use hashmap to memorize the state of the "needs" to speed up.But actually it gets slower since we need generate a hash_value of the "needs"

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

• Stackoverflow error on OJ for this input

``````[1,1]
[[1,1,2],[1,1,3]]
[4000,4000]
``````

• Line 9: java.lang.StackOverflowError

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

• What is the time complexity of this anyone ?

• 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.

• Does anyone know the time complexity of the above two solutions?

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.