“将一组瓶子里的水转移到另一个瓶子里”的算法（比喻意义下）。

Question

好的，我有一个问题。我有一组容器"A"，里面装满了各种大小的水。然后我又有另一组容器"B"，里面是空的。

我想要把A中的水转移到B中，知道每组容器的总容量相同。(即: A组含有与B组相同量的水)。

这个问题本身非常简单，只需将B中的第一个瓶子倒入A中的第一个瓶子，直到A中的瓶子装满为止。然后如果B中的瓶子还有剩余的水，就用A中的第二个瓶子接着倒，以此类推。

然而，我想要最小化倒水的总次数(每次从一个瓶子倒入另一个瓶子均计算为1次操作，无关于它涉及多少水)。

我想找到一个贪心算法来解决这个问题，或者至少找到一个有效的算法。但正确性比效率更重要(我不想得到一个次优的解决方案)。

当然，这个问题只是一个比喻，实际上是在管理个人开支的计算机程序中遇到的问题。

- luca

---

听起来像是背包问题。 - Oded

嗯...实际上这很不同，在那种情况下我们最大化金额，而这里金额无关紧要，只有"移动"操作才算。 - luca

Answer 1

不好的消息是：这个问题通过子集和问题的规约变得NP难。给定数字 x₁，…，x_n 和 S，子集和问题的目标是确定是否存在一些 x_i 的子集总和为S。我们用容量为 x₁，…，x_n 的 A-瓶和容量为S和(x₁+…+x_n-S)的 B-瓶制造，并确定是否足够进行 n 次倒注。

好消息是：任何贪心策略（即选择任意非空A、选择任意未填充的B，倒注直到必须停止）都是2近似算法（即使用的倒注次数最多是最优解的两倍）。最优解至少使用max(|A|，|B|)次倒注，而贪心方法最多使用|A|+|B|次，因为每次贪心做倒注时，要么排空一个A，要么填满一个B，不需要再次倒注。

可能会有一种近似方案（任何ε>0时都是（1 + ε）-近似）。我现在认为更可能有无法近似的结果 - 在这里通常用于获得近似方案的技巧似乎不适用。

---

以下是一些可能导致实际精确算法的想法。

给定一个解，用左顶点为A、右顶点为B的二分图绘制，并在仅当a倒入b时从a到b添加一条（无向）边。如果该解是最优解，则我声称没有循环 - 否则我们可以消除循环中最小的倒注并替换绕过循环的丢失体积。例如，如果我有下列倒注

a1 -> b1: 1
a1 -> b2: 2
a2 -> b1: 3
a2 -> b3: 4
a3 -> b2: 5
a3 -> b3: 6

然后我可以通过像这样倒入 a1 -> b1 来消除：

a2 -> b1: 4 (+1)
a2 -> b3: 3 (-1)
a3 -> b3: 7 (+1)
a3 -> b2: 4 (-1)
a1 -> b2: 3 (+1)

现在，由于该图没有环，我们可以将边的数量（倾倒量）计算为|A| + |B| - #(连通分量)。这里唯一的变量是连通分量的数量，我们希望最大化它。

我认为贪心算法形成的图没有环。如果我们知道最优解的连通分量是什么，我们可以在每个连通分量上使用贪心算法并得到最优解。

解决这个子问题的一种方法是使用动态规划枚举所有A的子集对X和B的子集对Y，使得sum(X) == sum(Y)，然后将它们输入到精确覆盖算法中。当然，这两个步骤都是指数级的，但它们在实际数据上可能表现良好。

- user635541

---

我认为我的答案是最优的，请看一下。 - Dan D.

不错的简化。但是我花了一会儿才明白你的意思是B有两个瓶子，一个容量为S，另一个容量为(x_1 + ... + x_n - S)——也许你可以更清楚地表达一下？ - j_random_hacker

Answer 2

以下是我的建议：

1. 识别在两组中具有完全相同大小的瓶子。这意味着这些相同大小的瓶子可以一对一地倒水。
2. 按容量将A中剩余的瓶子按降序排序，将B中剩余的瓶子按升序排序。计算将排序后的列表从A倒入B所需的倒水次数。

更新: 在第二步中每次倒水后，重复第一步。(由Steve Jessop建议的优化步骤)。反复执行此操作，直到所有水都被转移。

- shaolang

---

在第二阶段，部分倒空或部分倒满瓶子后，也许应该将其以新的大小（A中剩余的水量，B中剩余的空间）重新插入列表中？每次倾倒可能会额外增加O(log(n))的操作成本，但我认为如果这个解决方案的“排序列表”功能在第一次倾倒之前是有用的，那么在第二次倾倒之前也应该是有用的-基本上尽可能多地应用可用的工具来解决较小的问题。也许还应该重新检查相等的对，每次倾倒也需要O(log n)的操作成本。 - Steve Jessop

@Steve：有趣的优化。 :) - shaolang

不错..我认为这比上面的更好..但仍然不能很好地工作(例如，在Goran提供的示例中，它产生了7个步骤，而不是5个最佳步骤)，已经考虑了Steve建议的重新排序。 - luca

Answer 3

我认为这会给出最少的倾倒次数：

import bisect

def pours(A, B):
    assert sum(A) == sum(B)
    count = 0
    A.sort()
    B.sort()
    while A and B:
        i = A.pop()
        j = B.pop()
        if i == j:
            count += 1
        elif i > j:
            bisect.insort(A, i-j)
            count += 1
        elif i < j:
            bisect.insort(B, j-i)
            count += 1
    return count

A=[5,4]
B=[4,4,1]
print pours(A,B)
# gives 3

A=[5,3,2,1] 
B=[4,3,2,1,1]
print pours(A,B)
# gives 5

英文原文如下：

• 断言两个列表具有相同的总和（如果sum(A) > sum(B)或sum(A) < sum(B)为真，则算法仍将起作用）
• 取两个列表A和B，对它们进行排序

当A不为空且B不为空时：

• 从A中取出i（最大值），从B中取出j（最大值）
• 如果i等于j，则将i倒入j中并计数1次倒入
• 如果i大于j，则将i倒入j中，将i-j余数放回A中（使用插入排序），计数1次倒入
• 如果i小于j，则将i倒入j中，将j-i余数放回B中（使用插入排序），计数1次倒入

- Dan D.

---

例子，A={5,4}，B={4,4,1}。你的算法需要进行4次倒（分别是大小为4、1、3、1）。可以通过取消相同大小的单位或其他启发式方法找到一种只需要3次倒的解决方案。因此，我认为你的答案并没有给出最小的倒数，尽管它按要求计算得很高效 :-) - Steve Jessop

这可能会导致非常低效的解决方案（考虑瓶子大小偏移的情况，例如 A {5,3,2,1} B{4,3,2,1,1}）。 - Goran

不，它并不行。例如，A = {10, 4, 3}; B = {7, 6, 4} 的结果是需要倒5次，而不是最优的4次。你的百万美元奖金还得等等了。 - user635541

啊，要解决这个问题，你需要检查A是否有任何子集，其和等于B的当前j，并检查B是否有任何子集，其和等于A的当前i。好的，如果存在一个索引结构，其中包含A的{7：[4,3]}和B的{10：[6,4]}，并且被查询，那么它就可以找到这个解决方案。 - Dan D.

是的，尽管所需空间远远少于那个，但它确实以空间换时间，但为A列出子集和只需要最多sum(T(subset_sum(i, B)) for i in A)，而子集和问题有一个漂亮但NP解决方案，这就是为什么事先构建索引是有意义的；但是，人们需要一个索引到索引，以消除在删除A或B中的值时不可能的可能性。 - Dan D.