[Solved] how can i solve this problem of coins from n shop in python? [closed]

by


We can just pick the coin which shop has the largest. So the key point is the order of pick. I think you can use dfs to search all pick orders, and find the best one:

def pick_coins(demand, shops):
    # invalid input
    if sum(demand) > len(shops):
        return -1
    res = 0

    def dfs(demand, idx_remains, num):
        nonlocal res
        # all picked up
        if all(d == 0 for d in demand):
            # record it if it is max so far
            res = max(res, num)
            return

        for i, coin_num in enumerate(demand):
            if coin_num > 0:
                # which remain shop has max number of coin, and choose this one
                max_v, max_shop_idx = max((v[i], shop_idx) for shop_idx, v in enumerate(shops) if shop_idx in idx_remains)
                idx_remains.remove(max_shop_idx)
                demand[i] -= 1
                # do it recursively
                dfs(demand, idx_remains, num + max_v)
                # remember to revert the state when backtrack
                idx_remains.append(max_shop_idx)
                demand[i] += 1

    dfs(demand, list(range(len(shops))), 0)
    return res

def test():
    demand = [2, 1, 1]
    shops = [[5, 4, 5], [4, 3, 2], [10, 9, 7], [8, 2, 9]]
    print(pick_coins(demand, shops))    # output 27

Hope that will help you, and comment if you have further questions. : )

6

solved how can i solve this problem of coins from n shop in python? [closed]