"将水从一组瓶子转移到另一瓶子"的算法(比喻说)

Question

好的,我有一个问题.我有一套各种尺寸的瓶装"A",里面装满了水.然后我又拿了另一套各种尺寸的瓶子"B",都是空的.

我想将水从A转移到B,知道每组的总容量是相同的.(即:组A含有与组B相同的水量).

这当然是微不足道的,只需拿B中的第一个瓶子,倒入A中的第一个瓶子直到它满了.然后,如果B中的瓶子中还有水,请继续使用A中的第二个瓶子等.

但是,我想尽量减少浇注总量(从瓶子倒入另一个瓶子的动作,每个动作计数1,与其涉及的水量无关)

我想找到一个贪婪的算法来做到这一点,或者如果不可能,至少是一个有效的算法.然而,效率是算法正确性的次要因素(我不想要一个次优的解决方案).

当然,这个问题只是计算机程序中管理个人开支的真正问题的隐喻.

Answer 1

坏消息:通过减少子集和来解决这个问题.给定数字x ₁,...,x _n,S,子集和的对象是确定x _i的某个子集是否与S相加.我们制作容量为x ₁,...,x _n和B的A瓶- 容量为S和(x ₁ + ... + x _n - S)的瓶子,并确定n次浇注是否足够.

好消息:任何贪婪的策略(即,选择任何非空的A,选择任何未填充的B,倾倒直到我们必须停止)是2近似(即,最多使用两倍于最佳的倾倒).最优解决方案至少使用max(| A |,| B |)pours,而greedy最多使用| 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)

现在,由于图形没有周期,我们可以将边数(pours)计算为|A| + |B| - #(connected components).这里唯一的变量是我们想要最大化的连接组件的数量.

我声称贪心算法形成没有循环的图形.如果我们知道最佳解决方案的连接组件是什么,我们可以在每个解决方案上使用贪婪算法并获得最佳解决方案.

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