我如何在python中解决n店的硬币问题？

Question

有一个问题，我们给了n个商店，每个商店有3个硬币，即金，白金，钻石 客户必须获得最大的硬币 条件如下 他只能从一家商店购买最多一种类型的硬币 例如

INPUT

我有一个矩阵 4 <---没有商店 2 1 1 < - 最大数量我们可以有金，铂，钻石 5 4 5 < - shop 1有5枚金币，4枚铂金和5枚钻石币 4 3 2 < - 对于商店2 10 9 7 < - 对于商店3 8 2 9 < - 对于商店4

OUTPUT

答案是27 因为我们从1和3店采取金币，我们从shop2拿铂金币 我们从商店4拿钻石币 所以商店3和SHOP1 = 10 + 5 SHOP2 = 3 SHOP4 = 9 答案= 10 + 5 + 3 + 9 = 27

Answer 1

我们可以选择哪家商店拥有最大的硬币。所以关键点是选择的顺序。我想你可以使用dfs搜索所有的选择顺序，并找到最好的一个：

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

希望对您有所帮助，并在您有其他问题时发表评论。 :)