将数组按顺序分区

Question

这是我的一个朋友在面试中碰到的问题，我无法想出如何解决它。

问题：

给定一个有n个红色或蓝色按钮的数组。存在k个容器。容器的价值由其中红色和蓝色按钮的乘积给出。问题是将按钮放入容器中，使所有容器的价值之和最小。此外，所有容器必须包含按钮，并且必须按照它们给出的顺序放置。 例如，第一个按钮只能放在第一个容器中，第二个按钮可以放在第一个或第二个容器中，但不能放在第三个容器中（否则第二个容器就没有按钮了）。 k将小于或等于n。

我认为这个问题一定有一个动态规划的解决方案。

你如何解决这个问题？目前为止，我只得到了下面几种情况：

• 如果(n==k)，答案将为零，因为您可以将每个容器放置一个按钮，使每个容器的价值为零，因此总和将为零。
• 如果(k==1)，您只需倾倒所有按钮并计算乘积即可。
• 如果只有一种颜色存在，则答案将为零。

编辑：

我将给出一个例子。

n = 4，k = 2

输入：R B R R

第一个容器获取前两个（R和B），使其价值为1（1R X 1B）。 第二个容器获取剩余的（R和R），使其价值为0（2R x 0B）。 答案是1 + 0 = 1。

如果k = 3， 第一个容器只有第一个按钮（R） 第二个容器只有第二个按钮（B） 第三个容器将有最后两个按钮（R和R） 每个容器的价值都为0，因此总和和答案都为0。

希望这能消除疑虑。

- Coder25

---

如果 n >> k，并且我们在第 k + 1 步，所有容器到目前为止都只包含一个按钮，那么第 k + 1 个按钮可以放入任何一个容器吗？我不明白为什么不能把第二个按钮放入第三个容器。如果你有足够的按钮，你仍然可以稍后填充第二个容器。 - IVlad

很抱歉，但您的示例只会让我更加困惑。为什么不先将第一个 r 放入第一个容器中，将第二个 b 放入第二个容器中，然后将接下来的两个 r 放入第一个容器中，以获得总和为 0？ - IVlad

@IVlad：按钮必须按照给定的顺序放置。也就是说，前i个按钮放入第一个容器中，接下来的j个按钮放入第二个容器中，接下来的k个按钮放入第三个容器中，以此类推。 - Coder25

如果我理解正确，对于偶数k，总是可以使和为0。将相同颜色的按钮放在第一个容器中，当颜色改变时移动到下一个容器。对于奇数k，贪心算法是选择最后一个和第一个容器之间混合颜色，其他容器包含一种颜色。 - Ante

我想我终于理解了Coder25的问题。主要限制是您必须按顺序填充容器：也就是说，您有输入流R B R R，唯一可以执行的操作是“移动到下一个容器”（没有后退移动）。另一个定义是，给定来自{R，B}的长度为N元素和K个容器的序列，您需要提供K-1个索引，使得第i个容器将包含索引i和i + 1之间的元素。 - Matthieu M.

@Matthieu：我也这样理解。 - Ante

Answer 1

可能的动态规划解法：

令dp[i, j] = 将前i个数字放入j个容器中可能的最小数量。

dp[i, j] = min{dp[p, j - 1] + numRed[p+1, i]*numBlues[p+1, i]}, p = 1 to i - 1

答案将在dp[n, k]中。

int blue = 0, red = 0;
for (int i = 1; i <= n; ++i)
{
    if (buttons[i] == 1)
        ++red;
    else
        ++blue;

    dp[i][1] = red * blue;
}

for (int i = 2; i <= n; ++i)
    for (int j = 2; j <= k; ++j)
    {
        dp[i][j] = inf;

        for (int p = 1; p <= i; ++p)
            dp[i][j] = min(dp[p][j - 1] + getProd(p + 1, i), dp[i][j]);
    }

return dp[n][k];

复杂度将会是 O(n^3*k)，但是通过进行某些预计算可以使得 getProd 在 O(1) 的时间内运行，从而将复杂度降低至 O(n^2*k)（提示：使用 dp[i][1]）。如果在明天之前没有人发现这实际上是错误的话，我会发布它。

可能还可以将其降低至 O(n*k)，但是那可能需要不同的方法...

- IVlad

---

请问您能否解释一下这个解决方案？ - Coder25

@Coder25 - 如果我们知道了将1, 2, 3, ... i个数字放入1, 2, 3, ..., j个容器的答案，那么我们需要想办法利用这些信息来找到将i个数字放入j + 1个容器的答案。我们需要在1和i-1之间找到一个分割点p，使得数字1->p和p+1->i被放入两个不同的容器中。选择生成最小总和的分割点。 - IVlad

@lVlad：小问题--我对 p = 1 to i-1 表示怀疑，虽然它可能不会影响算法的正确性，并且可以证明是一种优化，但由于容器可能为空，我建议让 p 浮动直到包括 i。除此之外，算法似乎是正确的，尽管复杂度让人有些害怕...在实际实现中，我可能会添加一个检查，以便在 dp[i][j] 到达0时停止内循环（因为它不可能低于该值），但这并不改变最坏情况。 - Matthieu M.

@Matthieu M. - 听起来没错，我把它编辑成包括 i 在内。 - IVlad

Answer 2

警告：已被证明不是最优的

使用贪心算法来激发人们的谈话如何？我暂时不会试图证明它是最优的，但这是一种解决问题的方法。

在这个解决方案中，我们使用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  //total value: 0

0/3  2/0  1/1  0/2  3/0  //total value: 1

0/3  3/1  0/2  3/0  //total value: 3

0/3  3/1  3/2  //total value: 9

3/4  3/2  //total value: 18

我会保留这个答案，因为它已经达到了让人们谈论解决方案的唯一目的。我想知道是否可以在启发式搜索算法（如A*）中使用贪婪算法来提高穷举搜索的运行时间，但这并不能实现多项式运行时间。

- Mark Peters

---

我认为这个想法很好，但是你在细节上犯了错误：对于k==4，你不应该将4和5合并成总值为3吗？ - AShelly

@AShelly：哎呀，谢谢，我甚至不能按照自己的算法走！不过我认为这不会影响后面的算法，因为你只是在 k = 3 的时候折叠了 1/2；它们会交换。 - Mark Peters

只是提醒一下：我的直觉告诉我这不会是最优解。我现在不能花太多时间考虑证明草图。相反，我可能会稍后使用大量测试数据来尝试它，看看它在实践中是否有效。 - Mark Peters

我的直觉是这可能是最优解。我尝试在另一个答案中开始了证明。 - Jens Schauder

如果我没弄错的话，这个算法的时间复杂度应该是O(N(N-K))，比lVlad提出的DP解决方案更好。有人能够确认一下吗？ - Matthieu M.

马克，你的直觉是正确的，这不是最优的：考虑k=2时的oooxxoxooxxx。最优的分割在中间，总价值为16。你的算法第一步将会把中间的两个按钮分组，这是错误的（总价值将会是18）。 - Jules Olléon

Answer 3

如果我理解问题正确的话，只要每个容器里至少有一个按钮，你可以选择任何一个容器来放剩下的按钮。因此，在每个容器中放置一个按钮，确保至少有一个容器有红色按钮和至少有一个容器有蓝色按钮。然后，将所有剩余的红色按钮放入一个带有红色按钮的容器中，并将所有剩余的蓝色按钮放入一个带有蓝色按钮的容器中。这样每个容器都至少有一个按钮，而且每个容器只有一种颜色的按钮。然后每个容器的分数都为0。因此，总和为0，你已经最小化了组合得分。

- Becuzz

---

如果你的前k个按钮都是红色的，第k+1个是蓝色的，而你只有k+1个容器怎么办？根据问题描述，你需要使用所有容器，那么怎么知道将第k个按钮放入第一个容器并将第k个容器用于蓝色按钮呢？请问你能在此示例上运行你的算法吗？ - IVlad

这个问题有点令人困惑，但我认为“所有容器都必须包含按钮，并且它们必须按照给定的顺序放置”意味着即使每个容器都有一个按钮，顺序仍然很重要。因此，n[i+1]不能在比n[i]更早的容器中。如果我错了，请原作者纠正我。 - Andrew Clark

@Andrew 问题说明第二个按钮可以放入第一个或第二个容器，但不能放入第三个容器。这意味着第i个按钮可以放入前i-1个容器中的任何一个，但不能放在第i-1个容器之后的容器中，假设索引从0开始。 - efficiencyIsBliss

@efficiencyIsBliss 你说的是对的，我说的也是对的，它们并不互相矛盾。我的评论指出，如果按钮2放置在容器2中，则按钮3不能放置在容器1中。 - Andrew Clark

Answer 4

在面试中，我总是会要求对问题陈述进行澄清。想象一下，你从未将蓝色和红色按钮放在一起。那么它们的和就是0，就像n==k一样。因此，在所有k>1的情况下，最小值都为0。

- David

Answer 5

这里是一个用Python编写的暴力算法，看起来似乎可以工作。

from itertools import combinations
def get_best_order(n, k):
    slices = combinations(range(1, len(n)), k-1)
    container_slices = ([0] + list(s) + [len(n)] for s in slices)
    min_value = -1
    best = None
    def get_value(slices, n):
        value = 0
        for i in range(1, len(slices)):
            start, end = slices[i-1], slices[i]
            num_red = len([b for b in n[start:end] if b == 'r'])
            value += num_red * (end - start - num_red)
        return value
    for slices in container_slices:
        value = get_value(slices, n)
        if value < min_value or min_value == -1:
            min_value = value
            best = slices
    return [n[best[i-1]:best[i]] for i in range(1, len(best))]
n = ['b', 'r', 'b', 'r', 'r', 'r', 'b', 'b', 'r']
k = 4
print(get_best_order(n, k))
# [['b', 'r', 'b'], ['r', 'r', 'r'], ['b', 'b'], ['r']]

基本上，该算法的工作原理如下：

• 生成每种可能的排列列表（物品保持顺序，因此这只是每个容器中物品的数量）
• 根据 OP 的描述计算该排列的价值
• 如果该价值小于当前最佳价值，则保存它
• 返回具有最低价值的排列

- Andrew Clark

Answer 6

目前我所理解的是：该算法用于处理值序列{R,B}。如果有下一个容器，它可以选择将值放入当前容器或下一个容器中。

我首先会提出一些问题来澄清我还不知道的事情：

• 算法是否预先知道k和n？我认为是的。

• 我们是否预先知道完整的按钮序列？

• 如果我们不预先知道序列，平均值应该最小化吗？还是最大值（最坏情况）？

Mark Peters提出了一种证明算法的想法。

编辑：证明的想法（抱歉，无法在评论中适合）

令L(i)为第i组的长度。让d(i)表示通过折叠容器i和i+1得到的差异=> d(i) = L(i)*L(i+1)。

我们可以通过折叠包含较小索引的容器的折叠容器中包含原始容器的最大索引的序列来定义分布。

给定一系列崩溃 I = [i(1), .. i(m)]，其结果的下限等于从 1 到 n-k 的所有 m 的 d(i(m)) 总和。

我们需要证明除了由算法创建的序列之外，不能有其他序列具有更小的差异。因此，让上面的序列成为算法产生的序列。令 J = [j(1), .. j(m)]。

在这里，它变得简略： 我认为应该可以证明 J 的下限大于 I 的实际值，因为在每个步骤中，我们通过构造从 I 中选择崩溃操作，因此它必须小于来自备用序列的匹配崩溃。

我认为我们可以假设这些序列是不相交的，但我不完全确定。

- Jens Schauder

---

n、k和按钮序列已经提前给出。 - Coder25