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 nBA瓶-容量为 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 回答