AC python BFS solution


  • 0
    J

    The idea is simple. The lowest price shopping should be sum(x[i]*special[i]), where x[i] is the number of times a special offer is taken. The search process is the lowest price among all combinations of specials.

    For examples, special =[ [1, 1, 1], ], needs is [2, 2]. Then number of combination is 2(1 or 2 special offers) + 1(no offers) = 3

    The search space starts from 0 offers, then incrementally adds one offer based on a previous feasible plan. The new plan and unfilled needs are pushed into the queue. When processing each plan, cost is estimated and min_price is updated accordingly.

    To avoid duplicate plans, a plans_created set is maintained.

    The time complexity is # of possible offer combinations.

    class Solution(object):
        def shoppingOffers(self, price, special, needs):
            """
            :type price: List[int]
            :type special: List[List[int]]
            :type needs: List[int]
            :rtype: int
            """
            min_cost = sum(x*y for x, y in zip(needs, price))
            no_special = tuple([0]*len(special))
            plans_created, q = set([no_special]), collections.deque([(no_special, needs, min_cost)])
            while q:
                (prev_plan, prev_needs, prev_cost) = q.pop()
                # create new plans
                for i in xrange(len(special)):
                    needs, plan = prev_needs[:], list(prev_plan)
                    plan[i] += 1
                    if tuple(plan) in plans_created: continue
                    plans_created.add(tuple(plan))
                    needs = map(lambda j: needs[j]-special[i][j], xrange(len(price)))
                    if min(needs)<0: continue
                    cost = prev_cost + special[i][-1] - sum([x*y for (x, y) in zip(special[i], price)])
                    min_cost = min(min_cost, cost)
                    q.appendleft((tuple(plan), needs, cost))
            return min_cost
    

Log in to reply
 

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