10

好的，我有一个问题。我有一套“A”瓶大小不一的瓶子，都装满了水。然后我有另一组不同大小的瓶子“B”，都是空的。

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

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

但是，我想尽量减少倾倒的总数（从一个瓶子倒进另一个瓶子的动作，每个动作都算 1，与它涉及的水量无关）

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

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

4

3 回答 3

8

坏消息：这个问题是 NP-hard 通过从子集和减少。给定数字 x 1 , …, x n , S，子集求和的目的是确定 x 的某个子集是否与S 相加。我们制作容量为 x 1 、…、x n和B的A瓶-容量为 S 和 (x 1 + ... + x n - S) 的瓶子，并确定 n 次倾倒是否足够。

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

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

这里有一些想法可能会导致实用的精确算法。

给定一个解决方案，绘制一个具有左顶点A和右顶点以及从到B的（无向）边的二分图，当且仅当被注入时。如果解决方案是最佳的，我声称没有循环——否则我们可以消除循环中最小的倾倒并替换循环中丢失的体积。例如，如果我倒了abab

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| - #(connected components)。这里唯一的变量是我们想要最大化的连接组件的数量。

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

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

于 2011-02-27T14:04:07.437 回答
3

这是我的看法：

  1. 确定两组中尺寸完全相同的瓶子。这转化为这些相同尺寸瓶子的一对一倾倒。
  2. A中剩余瓶子按容量降序排序，B中剩余瓶子升序排序。计算将 A 到 B 中的排序列表倒入时所需的倒数。

更新：在第 2 步中每次倒入后，重复第 1 步。（Steve Jessop建议的优化步骤）。冲洗并重复，直到转移所有水。

于 2011-02-27T13:45:19.053 回答
0

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

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，将 ij 余数放回 A（使用插入排序），计数 1
  • 如果 i 小于 j，则将 i 倒进 j，将 ji 余数放回 B 中（使用插入排序），倒数 1
于 2011-02-27T13:45:33.933 回答