您如何确定如何将硬币放在时钟上？

Question

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

您被要求将这些硬币放置在 12 小时模拟钟面上，您放置的下一个硬币必须在前一个硬币之后 X 小时放置，其中 X 是前一个硬币的价值。

因此，如果您将 1 美分放在 12 上，则您放置的下一个硬币将变为 1。如果您将 5 美分放在 1 上，则您放置的下一个硬币将变为 6。以此类推。

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

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

Answer 1

不要采用贪婪的方法，而是尝试选择硬币与不选择硬币的最大结果。

def valueOfClock(capacity, coins, n, hour):
    if (n == 0 or capacity == 0 or hour > 12):
        return 0

    # Choose next coin if value is greater than the capacity
    if (coins[n-1] > capacity):
        valueOfClock(capacity, coins, n-1, hours)

    # Choose max value of either choosing the next coin or
    # choosing the current coin
    return max(valueOfClock(capacity, coins, n-1, hours),
               valueOfClock(capacity-coins[n-1], coins, n-1, hours + coins[n-1]))