我在工作中遇到了这个问题。我正在重新设计这个问题(从它最初的背景),以便它更容易理解。
你有几个有水能力的水桶。你的水壶只能倒进一些水桶里。罐子可以被部分清空成多个“允许的”桶。
你必须弄清楚,如果水罐和桶的配置,所有的水壶水可以转移到合法的桶,没有溢出。
示例:
假设你有A桶、B& C桶,它们分别有300、400和500台。
现在你有3罐J1,J2 & J3。他们分别有300,500和200单位的水。
注意,这个配置是可以解决的。一种可能的解决方案配置如下所示:
解决这个问题的最好方法是什么?我怀疑这可能是一种已知的算法。稍微谷歌一下就让我无处可寻。
我现在的试探性解决方案是,当我需要将水倒进一个特定的水桶时,要在水桶之间移动水(回溯)。请注意,我还没有完全冲掉它。
发布于 2013-06-04 05:44:31
这可以被看作是一个最大流量问题。
为每个水罐和每个桶创建一个源节点、一个接收器节点和节点,并在每个水罐中添加一个从源到每个水罐的边,其容量等于水罐中的水量。在允许的水罐/桶对之间添加具有无限容量的边,并从每个桶中向容量等于桶容量的接收器节点添加一条边。
现在找出最大流量。如果它等于总水量,那么你就有了一个解决方案。
https://stackoverflow.com/questions/16910393
复制相似问题