algorithm - 你如何确定如何将硬币放在时钟上？

Question

假设您有一组硬币，例如 4 10¢、4 5¢ 和 4 1¢。

您需要将这些硬币放在 12 小时模拟钟面上，您放置的下一枚硬币必须在前一枚硬币后 X 小时放置，其中 X 是前一枚硬币的值(value)。

因此，如果您在 12 上放置 1¢，那么您放置的下一个硬币将变为 1。如果您在 1 上放置 5¢，您放置的下一个硬币将变为 6。依此类推。

在必须将下一个硬币放入已占用的槽中之前，您如何才能最大限度地增加时钟上可以放置的硬币数量？

这是我遇到的一个问题，除非通过详尽搜索，否则我无法解决。如果输入是任意的，那么穷举搜索很快就会失败——假设它是任意数量的任意已知面额的硬币，时钟上有任意数量的小时数。那么你就不能再进行穷举搜索了，因为它变成了阶乘时间，并且会因为过多的计算时间要求而失败。

Answer 1

正如 maraca 提到的，可能没有比没有更多限制的回溯更好的解决方案了。也许给定面额的硬币数量更多，空间可以用“图案”覆盖。像硬币 [5, 10, 10, 5, 10, 10, 5, x] 覆盖前 8 个位置，下一枚硬币放置在与第一枚相似的位置。因此，如果有足够的硬币，可以重复该过程。

在这种情况下可能的硬币组合数量一点也不大。它是12!/(4! * 4! * 4!) = 34650。可以肯定的是，数字会随着参数的增加而爆炸。这是解决 3 倍大问题的简单 python 代码，该问题具有可能的硬币组合 3*10^15 .

max_positions = []
max_order = None

def add_coin(coins, position, coin_order, occupied_positions, num_hours):
    global max_positions, max_order
    if position in occupied_positions or not coins:
        # Can't place on that position or there is nothing more to place
        if len(occupied_positions) > len(max_positions):
            max_positions = occupied_positions
            max_order = coin_order
        return not coins  # if all is covered return true to stop search
    #
    for c, num_coins in coins:  # Try each coin
        # Copy coins to new list and remove one used
        c_coins = [x for x in coins if x[0] != c]
        if num_coins > 1:
            c_coins.append((c, num_coins-1))
        # Next iteration
        if add_coin(c_coins,
                 (position + c) % num_hours,
                 coin_order + [c],
                 occupied_positions + [position],
                 num_hours):
            return True

def solve_coins(coins, num_hours):
    global max_positions, max_order
    max_positions = []
    max_order = None
    add_coin(coins, 0, [], [], num_hours)
    print len(max_positions), max_positions, max_order

solve_coins([(1, 4), (5, 4), (10, 4)], 12)
solve_coins([(1, 8), (5, 8), (10, 8)], 24)
solve_coins([(1, 12), (5, 12), (10, 12)], 36)

输出:

12 [0, 1, 6, 4, 2, 3, 8, 9, 7, 5, 10, 11] [1, 5, 10, 10, 1, 5, 1, 10, 10, 5, 1, 5]
24 [0, 1, 6, 16, 17, 3, 4, 14, 19, 5, 15, 20, 21, 2, 7, 8, 13, 18, 23, 9, 10, 11, 12, 22] [1, 5, 10, 1, 10, 1, 10, 5, 10, 10, 5, 1, 5, 5, 1, 5, 5, 5, 10, 1, 1, 1, 10, 10]
36 [0, 1, 6, 16, 17, 22, 23, 28, 2, 12, 13, 18, 19, 29, 34, 3, 8, 9, 10, 11, 21, 31, 5, 15, 20, 30, 35, 4, 14, 24, 25, 26, 27, 32, 33, 7] [1, 5, 10, 1, 5, 1, 5, 10, 10, 1, 5, 1, 10, 5, 5, 5, 1, 1, 1, 10, 10, 10, 10, 5, 10, 5, 5, 10, 10, 1, 1, 1, 5, 1, 10, 5]