警告:已被证明不是最优的
使用贪心算法来激发人们的谈话如何?我暂时不会试图证明它是最优的,但这是一种解决问题的方法。
在这个解决方案中,我们使用G来表示按钮序列中一种颜色连续区域的数量。假设我们有以下序列(我使用x代表红色,o代表蓝色,因为R和B看起来太相似了):
x x x o x o o o x x o
这将给出 G = 6。让我们将其分成红色和蓝色两组,一开始每组都获得一个具有一致颜色的区域:
3/0 0/1 1/0 0/3 2/0 0/1 //total value: 0
当G≤k时,每个分组都可以放入自己的容器,因此最小值为零。现在假设G>k。我们的贪心算法是,只要有更多的分组比容器多,就将两个相邻的分组合并成一个,使容器值差异最小(merged(a, b)的valueOf() - a的valueOf() - b的valueOf())。假设k=5,根据上面的例子,我们的选择如下:
Collapse 1,2: delta = (3 - 0 - 0) = 3
2,3: delta = 1
3,4: delta = 3
4,5: delta = 6
5,6: delta = 2
所以我们将2和3合并:
3/0 1/1 0/3 2/0 0/1 //total value: 1
当 k = 4 时:
Collapse 1,2: delta = (4 - 0 - 1) = 3
2,3: delta = (4 - 1 - 0) = 3
3,4: delta = (6 - 0 - 0) = 6
4,5: delta = 2
3/0 1/1 0/3 2/1 //total value: 3
k = 3
4/1 0/3 2/1 //total value: 6
k = 2
4/1 2/4 //total value: 12
k = 1
6/5 //total value: 30
这看起来对于这种情况是最优的,但我只是想让人们讨论一个解决方案。请注意,将按钮分配给容器的起始方式是一种捷径:您可以从每个按钮按顺序放入自己的桶开始,然后缩小范围,但您总会到达每个容器具有一个颜色的最大按钮数量的点。
反例:感谢Jules Olléon提供了一个反例,这是我懒得想的。
o o o x x o x o o x x x
如果 k = 2,最优映射为:
2/4 4/2 //total value: 16
让我们看看贪心算法如何解决这个问题:
0/3 2/0 0/1 1/0 0/2 3/0
0/3 2/0 1/1 0/2 3/0
0/3 3/1 0/2 3/0
0/3 3/1 3/2
3/4 3/2
我会保留这个答案,因为它已经达到了让人们谈论解决方案的唯一目的。我想知道是否可以在启发式搜索算法(如A*)中使用贪婪算法来提高穷举搜索的运行时间,但这并不能实现多项式运行时间。
n >> k
,并且我们在第k + 1
步,所有容器到目前为止都只包含一个按钮,那么第k + 1
个按钮可以放入任何一个容器吗?我不明白为什么不能把第二个按钮放入第三个容器。如果你有足够的按钮,你仍然可以稍后填充第二个容器。 - IVladr
放入第一个容器中,将第二个b
放入第二个容器中,然后将接下来的两个r
放入第一个容器中,以获得总和为0
? - IVladCoder25
的问题。主要限制是您必须按顺序填充容器:也就是说,您有输入流R B R R
,唯一可以执行的操作是“移动到下一个容器”(没有后退移动)。另一个定义是,给定来自{R,B}
的长度为N
元素和K
个容器的序列,您需要提供K-1
个索引,使得第i
个容器将包含索引i
和i + 1
之间的元素。 - Matthieu M.