How to reduce the time complexity of this algorithm?

Question

I provide two data structures, cart_info and map_case, and get the result real_combinationby the algorithm.

This algorithm is implemented in python

import itertools

cart_info = {'a':1, 'b':2, 'c':2, 'd':1}
map_case = {
    'm':[{'a':1,'c':1,'coupon':'m','discount_amount':2}, {'b':2,'c':1,'coupon':'m','discount_amount':3}],
    'n':[{'d':1,'c':1,'coupon':'n','discount_amount':1}, {'b':1,'d':1,'coupon':'n','discount_amount':4}],
    'p':[{'c':1,'b':2,'coupon':'p','discount_amount':3}, {'c':1,'coupon':'p','discount_amount':1}]

}
map_case_key = map_case.keys()
real_combination = []

for i in range(len(map_case_key)):
    combination = list(itertools.combinations(map_case_key, i+1))
    for case in combination:
        sample = [map_case[x] for x in case]
        all_output = list(itertools.product(*sample))
        for result in all_output:
            _cart = {}
            for x in result:
                for k,v in x.items():
                    if k in ('coupon','discount_amount'):
                        continue
                    elif k not in _cart:
                        _cart[k] = v
                    else:
                        _cart[k] = _cart[k] + v
            flag = True
            for x in _cart:
                if _cart[x] > cart_info[x]:
                    flag = False
                    break
            if flag:
                real_combination.append(result)

real_combination.sort(key=lambda x:sum(i['discount_amount'] for i in x),reverse=True)
print(real_combination)

The result of real_combinationis

[({'a': 1, 'c': 1, 'coupon': 'm', 'discount_amount': 2}, {'b': 1, 'd': 1, 'coupon': 'n', 'discount_amount': 4}, {'c': 1, 'coupon': 'p', 'discount_amount': 1}), ({'a': 1, 'c': 1, 'coupon': 'm', 'discount_amount': 2}, {'b': 1, 'd': 1, 'coupon': 'n', 'discount_amount': 4}), ({'a': 1, 'c': 1, 'coupon': 'm', 'discount_amount': 2}, {'c': 1, 'b': 2, 'coupon': 'p', 'discount_amount': 3}), ({'b': 1, 'd': 1, 'coupon': 'n', 'discount_amount': 4}, {'c': 1, 'coupon': 'p', 'discount_amount': 1}), ({'b': 1, 'd': 1, 'coupon': 'n', 'discount_amount': 4},), ({'b': 2, 'c': 1, 'coupon': 'm', 'discount_amount': 3}, {'d': 1, 'c': 1, 'coupon': 'n', 'discount_amount': 1}), ({'b': 2, 'c': 1, 'coupon': 'm', 'discount_amount': 3}, {'c': 1, 'coupon': 'p', 'discount_amount': 1}), ({'d': 1, 'c': 1, 'coupon': 'n', 'discount_amount': 1}, {'c': 1, 'b': 2, 'coupon': 'p', 'discount_amount': 3}), ({'b': 2, 'c': 1, 'coupon': 'm', 'discount_amount': 3},), ({'c': 1, 'b': 2, 'coupon': 'p', 'discount_amount': 3},), ({'a': 1, 'c': 1, 'coupon': 'm', 'discount_amount': 2}, {'d': 1, 'c': 1, 'coupon': 'n', 'discount_amount': 1}), ({'a': 1, 'c': 1, 'coupon': 'm', 'discount_amount': 2}, {'c': 1, 'coupon': 'p', 'discount_amount': 1}), ({'a': 1, 'c': 1, 'coupon': 'm', 'discount_amount': 2},), ({'d': 1, 'c': 1, 'coupon': 'n', 'discount_amount': 1}, {'c': 1, 'coupon': 'p', 'discount_amount': 1}), ({'d': 1, 'c': 1, 'coupon': 'n', 'discount_amount': 1},), ({'c': 1, 'coupon': 'p', 'discount_amount': 1},)]

Is there a better algorithm to get the same result? How to reduce the time complexity of this algorithm.

There are two pieces of information entered. One is the cart_info, in which each key-value pair indicates its item and quantity correspondence. The other is the map_case where the key-value pairs indicate the combination of each shopping coupon used individually in the shopping cart and the discount price corresponding to such combination.Each coupon can only be used once, and the used item will be deducted from the shopping cart after use.It is trying to find out what is the maximum cart discount amount and how to apply coupons in the case.