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]
    

Log in to reply
 

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