经典圆桌算法？

Question

不同面值的硬币围绕着一张圆桌散布。我们可以选择任何硬币，使得对于任何两个相邻的硬币对，必须至少选择一个(两个都可以选择)。在这种情况下，我们必须找到所选硬币的最小可能值。

我必须考虑时间复杂性，所以我尝试使用动态编程，而不是使用朴素的递归暴力。但是我得到了错误的答案--我的算法是错误的。

如果有人能提出一个动态的算法，我就可以用c++编写代码了。另外，硬币的最大数量是10^6，所以我认为存在O(n)解。

编辑:好的，我还添加了一个示例。如果桌子周围的硬币价值是1,2,1,2,2 (圆圈)，那么通过选择第一，第三和第四(或第五)，硬币的最小价值将是4。

Answer 1

我认为下面的算法会给你带来最好的解决方案。我还没有看过你的代码(抱歉)：

我们将在圆中选择一个随机点作为起点。假设它是1。我们将看看如果它被选中会发生什么。

所以我们选择1。在圆圈中向上移动，你可以选择选择2或不选择2。这可以在树中显示，其中顶部的分支表示选择硬币，而下面的分支表示不选择硬币。这些数字表示所选硬币的总和。

   3 = 1 and 2 both selected
  /
1
  \
   1 = 1 selected, 2 not

现在我们继续循环，可以选择3或不选择3。这给出了一个类似于

         6 = 1, 2 and 3 selected
       /
     3
    /  \
   /     3= 1 and 2 selected, 3 not
  /
1
  \
   \     4 = 1 and 3 selected, 2 not 
    \  /
     1 
      \
        1 = 1 selected, 2 and 3 not

现在在那棵树上，我们可以修剪了！给出你的问题陈述，你必须跟踪哪些硬币被拿走，以确保每一枚硬币都被“覆盖”。假设最后两枚硬币没有被选中。那么你就知道，为了不违反你的约束，必须选择下一个。更重要的是，算法的其余部分的可能性只取决于最后两个硬币的选择。

现在看看所有选择了最后一枚硬币的分支(3)。你只需要保留重量最轻的那个。这两个分支都可以自由选择算法的其余部分。在这种情况下，我们可以安全地删除顶部分支。然后我们剩下3条可能的路径。

现在让我们看一下，如果我们列举硬币4的选择会发生什么

     3      7= 1, 2 and 4 selected, 3 not
    /  \   /
   /     3
  /       \
           3 =  1 and 2 selected, 3 and 4 not 
1          8 = 1, 3 and 4 selected, 2 not 
  \       /
   \     4 
    \  /  \
     1     4 = 1 and 3 selected, 2 and 4 not 
           5 = 1 and 4 selected, 2 and 3 not
      \  /
        1 
         \
           1 = only 1 selected

现在你有6个选择。但是，最低的分支(仅选择1)是无效的，因为3与任何东西都不相邻。您可以将其修剪为剩下5个分支。在这5枚硬币中，有3枚选择了4枚(=到目前为止的最后一枚硬币)，我们可以像以前一样做同样的事情:只保留最便宜的分支。这再次将分支的数量减少到3个。

你可以在你的整个圆圈中继续这样做，直到你再次到达起点。那么你应该有3条路径，你可以从中选择最便宜的。如果您从选择硬币1开始，这将为您提供最佳解决方案。

现在我们有了当选择1时的最佳解决方案。但是，可能不应选择%1。它可能与另一个选择的硬币相邻:硬币2或硬币6。如果我们现在对硬币2而不是硬币1执行上述算法一次，然后对硬币6执行一次，我们应该会有最佳解决方案。

这种方法依赖于硬币1、2或6被选择的事实。

我希望我的方法是可以理解的。它相当长，你可以通过使用一些状态转换图来更快地完成它，在这个图中，你只维护可能的状态(这取决于最后两个硬币)，并在此基础上工作。方法与上面相同，只是更紧凑)

Answer 2

把所有东西都放在一个圆圈里会妨碍动态编程，因为没有稳定的起点。

如果你知道一个特定的硬币会包含在最佳答案中，你可以把它作为你的起点。将其重新编号为硬币1，并使用动态编程计算出1..N的最佳成本，选择和不选择第N个硬币。考虑到这一点，您可以计算出1..N+1的最佳成本等等。

实际上，如果有人告诉你某个硬币不会被选中，你也可以使用这种方法-你只是有稍微不同的开始条件。或者您可以利用这一事实，如果您知道某个特定的硬币未被选中，则必须选择其两侧的两个硬币。

任何硬币都被选中或未选中，因此您可以通过解决两个动态编程问题来双向查看成本，并选择最便宜的成本。

Answer 3

O(n)建议，通过归纳。嗯，我现在读了维基，我发现它也算动态编程。这是一个非常宽泛的术语。我以前对动态编程有不同的理解。

词汇表

我们在N places有N硬币。硬币价值是a[i]，其中0 <= i < N。可以选择或取消选择每个硬币，我们将其表示为0和1的序列。

算法描述

00在任何地方都是无效的序列，因为它会违反问题约束。111也是无效的，因为它不是最优的，101总是更好。

依次对于每个位置i，我们计算3个最佳和，对于3个代码：01，10，11。代码来自最后两个硬币的设置，即i-1和i。所以我们在变量b01，b02，b11中有最佳(最小)和。

我们必须从一些确定的东西开始，所以我们将应用算法2次。一张是0号位置的硬币，另一张是未放的。

一开始，我们尝试places 0和1，并直接启动bs。b01 = a[1]，b10 = a[0]，b11 = a[0] + a[1]。然而，如果这一轮我们选择第一枚硬币未设置，我们只能接受b01解决方案。所以我们给b10和b11分配了一个很大的数字。这些解决方案将被下一步算法快速删除。在第二轮中，我们将做相反的事情:将较大的nuber赋值给b01，因为必须设置第一位。

在步骤i，我们得到了place i-1 in bs的最佳和，我们计算cs，这是place i的最佳和。

c01 = b10 + a[i]    // 101 (10 -> 01)
c10 = min(b01, b11) // 010 (01 -> 10) or 110 (11 -> 10)
c11 = b01 + a[i]    // 011 (01 -> 11)

这来自于以下可能性：

010 - b01 -> c10
011 - b01 -> c11
100 - invalid
101 - b10 -> c01
110 - b11 -> c10
111 - invalid

当然，我们在结束每一步的时候，都会将最佳和赋给b。

当我们处理所有硬币时，我们必须丢弃与初始假设不兼容的解决方案。位i-2、i-1和0必须生成有效序列。

这是run 123456 sequence示例。

A.假设第一位为0

1 a[1] = 2: b01 = 2, b10 = 999, b11 = 999
2 a[2] = 3: b01 = 1002, b10 = 2, b11 = 5
3 a[3] = 4: b01 = 6, b10 = 9, b11 = 1006
4 a[4] = 5: b01 = 13, b10 = 6, b11 = 11
5 a[5] = 6: b01 = 12, b10 = 13, b11 = 19

b10是不可接受的，我们从b01和b11中选择更好的，它是12。

B.假设第一位为1

1 a[1] = 2: b01 = 999, b10 = 1, b11 = 3
2 a[2] = 3: b01 = 4, b10 = 3, b11 = 1002
3 a[3] = 4: b01 = 7, b10 = 4, b11 = 8
4 a[4] = 5: b01 = 9, b10 = 12, b11 = 12
5 a[5] = 6: b01 = 18, b10 = 9, b11 = 15

现在b11是无效的，因为它会产生111。因此我们选择b01和b10中最好的，即9。步骤A给出12，步骤B给出9。9更好。这就是结果。

上面的计算是我手动完成的，如果有错误，我深表歉意。然而，对于第一个未设置的硬币，我计算了2+4+6，对于第一个设置的硬币，结果是1+3+5。似乎是正确的。