首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >聪明地用水桶储存水--算法建议?

聪明地用水桶储存水--算法建议?
EN

Stack Overflow用户
提问于 2013-06-04 05:26:57
回答 1查看 414关注 0票数 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. 来自J2的C-100个单元和来自J3的200个单元使这个桶能够填充500 - (100 + 200) =200个单元。

解决这个问题的最好方法是什么?我怀疑这可能是一种已知的算法。稍微谷歌一下就让我无处可寻。

我现在的试探性解决方案是,当我需要将水倒进一个特定的水桶时,要在水桶之间移动水(回溯)。请注意,我还没有完全冲掉它。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-06-04 05:44:31

这可以被看作是一个最大流量问题。

为每个水罐和每个桶创建一个源节点、一个接收器节点和节点,并在每个水罐中添加一个从源到每个水罐的边,其容量等于水罐中的水量。在允许的水罐/桶对之间添加具有无限容量的边,并从每个桶中向容量等于桶容量的接收器节点添加一条边。

现在找出最大流量。如果它等于总水量,那么你就有了一个解决方案。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/16910393

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档