坏消息:这个问题是 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
的(无向)边的二分图,当且仅当被注入时。如果解决方案是最佳的,我声称没有循环——否则我们可以消除循环中最小的倾倒并替换循环中丢失的体积。例如,如果我倒了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| - #(connected components)
。这里唯一的变量是我们想要最大化的连接组件的数量。
我声称贪心算法形成了没有循环的图。如果我们知道最优解的连通分量是什么,我们可以对每个分量使用贪心算法并得到最优解。
解决这个子问题的一种方法是使用动态编程来枚举 A 的所有子集对 X 和 B 的 Y 使得 sum(X) == sum(Y) 然后将它们输入到精确的覆盖算法中。这两个步骤当然是指数级的,但它们可能在真实数据上运行良好。