“将水从一组瓶子转移到另一组瓶子”的算法（比喻地讲）

Question

好吧，我有问题。我有一组“A”各种尺寸的瓶子，里面装满了水。 然后我还有另一组“B”各种尺寸的瓶子，全是空的。

我想将水从A转移到B，知道每组的总容量是相同的。 （即：A 组含有与 B 组相同量的水）。

这本身当然是微不足道的，只需将 B 中的第一个瓶子倒入 A 中的第一个瓶子中，直到装满即可。然后，如果 B 中的瓶子里还有水，则继续 A 中的第二个瓶子，依此类推。

但是，我想最小化倒水的总数（从一个瓶子倒到另一个瓶子的动作，每个动作计 1，独立于它涉及多少水）

我想找到一种贪婪算法来做到这一点，或者如果不可能的话至少是一种有效的算法。然而，效率对于算法的正确性来说是次要的（我不想要次优的解决方案）。

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

Answer 1

坏消息：这个问题是 NP 困难的，因为子集和减少了。给定数字 x₁, …, x_n, S，子集和的目的是确定 x_i 是否存在某个子集s 总和为 S。我们制作容量为 x₁, …, x_n 的 A 瓶，以及容量为 S 和 (x₁ 的 B 瓶> + … + x_n - S) 并确定 n 次浇注是否足够。

好消息：任何贪婪策略（即，选择任何非空 A，选择任何未填充的 B，倾倒直到我们必须停止）都是 2 近似（即，最多使用最佳倾倒次数的两倍）。最优解至少使用 max(|A|, |B|) 次，而贪婪则最多使用 |A| + |B|，因为贪婪每次倾倒时，要么 A 被排空，要么 B 被填充，并且不需要再次倒出或倒入。

可能有一个近似方案（a (1 + ε)-对任何 ε > 0 的近似）。 我认为现在更有可能存在不可近似结果 - 获得近似方案的常用技巧并不适用似乎不适用这里。

---

以下是一些可能会产生实用的精确算法的想法。

给定一个解决方案，绘制一个二分图，其左顶点 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) ，然后将它们输入精确覆盖算法。这两个步骤当然都是指数级的，但它们可能适用于真实数据。

Answer 2

我的看法是：

1. 找出两组中尺寸完全相同的瓶子。这意味着对这些相同尺寸的瓶子进行一对一的倾倒。
2. 将 A 中剩余的瓶子按容量降序排序，将 B 中剩余的瓶子按容量升序排序。计算将 A 中的排序列表浇注到 B 时所需的浇注次数。

更新：在步骤 2 中每次浇注后，重复步骤 1。（史蒂夫·杰索普）。冲洗并重复直至所有水都被转移。

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) is true)
• 取两个列表 A 和 B，

在 A 不为空且 B 不为空时对它们进行排序：

• 取 i（最大的）从 A 和 j（最大的）从 B
• 如果 i 等于 j，将 i 倒入 j 并计数 1
• 如果 i 大于 j，将 i 倒入 j，将 ij 余数放回 A（使用插入排序），计数 1 pour
• 如果 i 小于 j，则将 i 倒入 j，将 ji 余数放回到 B 中（使用插入排序），计数 1 pour