Shopping Offers


  • 0

    Click here to see the full article post


  • 0
    A

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


  • 0

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


  • 0
    S

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


  • 0

    @szp_14163.com Could you please share your approach here?


  • 0
    N

    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.


  • 0
    S

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


  • 0
    A

    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"


  • 0
    A

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


  • 0

    Stackoverflow error on OJ for this input

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

  • 0

    Line 9: java.lang.StackOverflowError


  • 0
    J

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


  • 0
    C

    What is the time complexity of this anyone ?


Log in to reply
 

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