我不知道描述问题的名称,所以我只是要设置一个示例,并寻求比蛮力解决更好的算法的帮助。
有 6 个桶,每个桶都有不同的大小,每个桶容纳不同的起始体积。每个桶还有一个指向奖品价值的链接 - 称之为金钱 - 当桶装满时分配。
有8个阀门。每个阀门在打开时为不同的桶子集供料,并且每个桶在阀门打开时可以获得不同的添加量。每个阀门都有固定的转动成本。
部分示例:桶 1:20 加仑中的 14 加仑。支付 2.00 美元 桶 2:25 加仑中的 12 加仑。支付 1.50 美元桶 3:35 加仑中的 18 加仑。支付 4.00 美元等...
阀门 1:成本 0.50 美元。将 2 加仑放入 2 中,将 1 加仑放入 3 中。阀门 2:成本 0.40 美元。将 3 加仑放入 1 中,将 5 加仑放入 2 中,依此类推...
因此,您支付一些钱来转动阀门,如果您装满水桶,您就会赢得一些钱。
目标:如果存在任何有利可图的组合,则计算当桶装满时阀门的最佳顺序以实现最大利润。
当桶装满时,它会重置为预设的起始体积(可能与其当前体积不同 - 桶在阀门转动到阀门转动时保持状态)。从理论上讲,重置次数没有限制,因此可能会永远转动阀门。
这里明显的解决方案是蛮力。将变量重置为起始位置,转动一个阀门,测试输出,重置,迭代到下一个阀门,等等。在所有 8 个阀门都转动之后,开始转动两个阀门(11、12、13、14,... 25、26 , 27, 28)。每次您找到一个组合至少能填满一个桶时,计算净收益/损失并与之前的结果进行比较以确定最佳组合。
缓慢而粗暴。相当直接,但缓慢而粗暴。
所以:
- 这类问题的名称是什么?和
- 是否有已知的算法可以帮助更有效地解决它?
需要明确的是 - 数学细节不是需要改进的位 - 我可以轻松计算任何阀门操作序列的结果,而不管数学上的微小变化。
这是我想避免的蛮力迭代。我不想做 8 个单操作(v1、v2、v3...),然后是 64 个双操作(v1v1、v1v2、v1v3 等),然后是 512 个三操作(v1v1v1、v1v1v2、v1v1v3),如果我可以避免。