3

我在工作中遇到了这个问题。我正在重新定义问题（从其原始上下文），以便更容易理解。

您有几个具有承水能力的水桶。您的水壶只能倒入特定的桶中。罐子可以部分清空到多个“允许”的桶中。

您必须确定在给定水壶和桶配置的情况下，所有壶水是否可以转移到合法的桶中而不会溢出。

例子：

假设您有存储桶 A、B 和 C。它们的容量分别为 300、400 和 500 个单位。

现在您有 3 个水壶 J1、J2 和 J3。它们分别有 300、500 和 200 个单位的水。

  1. J1可以清空到A&B
  2. J2可以清空到A、B&C
  3. J3可以清空成C

注意这个配置是可以解决的。一种可能的解决方案配置可能如下所示：

  1. A - J1 在这里完全清空 - 不能再装满这个桶了
  2. B - J2 在这里完全清空 - 不能再装满这个桶了
  3. C - 来自 J2 的 100 个单位和来自 J3 的 200 个单位离开这个桶，能够填充 500 - (100 + 200) = 200 个单位以上

解决这个问题的最佳方法是什么？我怀疑这可能是一个已知的算法。一点谷歌搜索让我无处可去。

我现在的暂定解决方案包括当我需要将水倒入特定的水桶时在水桶之间移动水（回溯）。请注意，我还没有完全冲洗掉它。

4

1 回答 1

4

这可以被视为最大流量问题。

为每个水罐和每个桶创建一个源节点、一个汇节点和节点，并从源向每个水罐添加一条边，其容量等于该水罐中的水量。在允许的水罐/桶对之间添加容量无限的边，并将每个桶的边添加到容量等于桶容量的汇节点。

现在找到最大流量。如果它等于水的总量，那么你有一个解决方案。

于 2013-06-04T05:44:31.003 回答