0

我正在尝试解决这个问题：

假设我有一组 n 个硬币 {a_1, a2, ..., a_n}。价值为 1 的硬币总是会出现。我需要达到 M 的最少硬币数量是多少？

约束是：

  • 1≤n≤25
  • 1≤m≤10^6
  • 1 ≤ a_i ≤ 100

好的，我知道这是变革问题。我尝试使用广度优先搜索、动态规划和贪婪来解决这个问题（这是不正确的，因为它并不总是提供最佳解决方案）。但是，我超过了时间限制（3 秒）。

所以我想知道是否有针对这个问题的优化。描述和限制引起了我的注意，但我不知道如何使用它对我有利：

  • 价值为 1 的硬币总是会出现。
  • 1 ≤ a_i ≤ 100

我在维基百科上看到这个问题也可以通过“使用概率卷积树进行动态编程”来解决。但我什么都听不懂。

你能帮助我吗？这个问题可以在这里找到：http: //goo.gl/nzQJem

4

1 回答 1

1

让我们a_n成为最大的硬币。使用这两个线索：

  • 结果是>= ceil(M/a_n)，
  • 结果配置有很多a_n's。

最好尝试使用最大值，a_n's而不是检查是否有更好的结果，a_n's直到有可能找到更好的结果。

类似于：让R({a_1, ..., a_n}, M)函数返回给定问题的结果。比R可以实现：

num_a_n = floor(M/a_n)
best_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n)
while num_a_n > 0:
  num_a_n = num_a_n - 1
  # Check is it possible at all to get better result
  if num_a_n + ceil(M-a_n*num_a_n / a_(n-1) ) >= best_r:
     return best_r
  next_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n)
  if next_r < best_r:
    best_r = next_r
return best_r
于 2014-09-14T11:09:54.097 回答