好的，我有一个问题。我有一套各种尺寸的瓶装“A”，里面装满了水。 然后我有另一套“B”的各种尺寸的瓶子，都是空的。
我想将水从A转移到B，知道每组的总容量是相同的。 （即：A组含有与B组相同的水量）。
这当然是微不足道的，只需拿B中的第一个瓶子，倒入A中的第一个瓶子直到它满了。然后，如果B中的瓶子中还有水，请继续使用A中的第二个瓶子等。
但是，我想尽量减少浇注总量（从瓶子倒入另一个瓶子的动作，每个动作计数1，独立于它涉及多少水）
我想找到一个贪婪的算法来做到这一点，或者如果不可能，至少是一个有效的算法。然而，效率是算法正确性的次要因素（我不想要一个次优的解决方案）。
当然，这个问题只是计算机程序中管理个人开支的真正问题的隐喻。
坏消息：通过减少子集和来解决这个问题。给定数字x1， …， Xñ，S，子集和的对象是确定x的某个子集一世总和到S.我们生产容量为x的A瓶1， …， Xñ 容量为S和（x1 + ... + xñ - S）并确定n注入是否足够。
好消息：任何贪婪的策略（即，选择任何非空的A，选择任何未填充的B，倾倒直到我们必须停止）是2近似（即，最多使用两倍于最佳的倾倒）。最优解决方案至少使用max（| A |，| B |），最多使用贪婪| A | + | B |，因为每次贪婪倾倒时，要么A被排空，要么B被填满，不需要倒出或重新注入。
可能存在近似方案（对于任何ε> 0，a（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），然后将它们馈送到精确的覆盖算法中。这两个步骤当然都是指数级的，但它们可能在真实数据上运行良好。
这是我的看法：
更新： 在步骤2中每次浇注后，重复步骤1.（建议的优化步骤 史蒂夫杰索普）。冲洗并重复直至所有水都转移。
我认为这给出了最小的倒水次数：
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不为空：