MIB的总部有N个水箱。坦克i最多可以储存c i个单位的水。每个水箱都有自己的进出管。水箱i的进水管以u i的速率漏水，这意味着如果我们想将 100 单位的水放入水箱i中，将消耗100/(1 - u i ) 的水。出水管都是完美的。它们的容量是in i和out i，这意味着罐i的进水管最多可以携带in i 。单位时间内的水量（包括漏水量），出水管单位时间内最多可带出i单位水量。
整数序列w t (1 < t < T) 表示可以放入或必须从该储水系统中取出多少水。例如 (5, 3, -8, 10) 表示系统在第 1、2、4 个时间段最多可以进水 5、3 和 10 个单位的水，在第 3 个时隙必须出 8 个单位的水时隙。出水量超标称为不可行（超标即可）。问题是，给定每个坦克的参数（c i , u i , in i , out i）和序列w t，天气满足所有插座要求是否可行？在时间 0，所有水箱都是空的。
N < 10,000, T < 10,000
谢谢
首先，这是一个不能单独工作的方案，因为它忽略了对最大流入和流出率的约束，因此它解决了一个更简单的问题。
这里棘手的一点似乎是何时使用哪个坦克。看起来 Ui 值较低的坦克更好。如果您采用任何序列填充具有高 Ui 值的水箱而有一个具有较低 Ui 值的水箱有空间，那么您可以通过先填充更好的水箱来获得更好的序列，然后使用额外的水您将使用本来会放入更糟糕的水箱中的水。同样，如果您在好水箱中有水的情况下从坏水箱中取水，则可以通过从好水箱中提取水来获得更好的顺序，这样您就有机会在本来要加水的情况下加水坦克。
所以看起来，当你装满一个水箱时，你想装满可用的最好的水箱，而当你清空一个水箱时，你想清空可用的最好的水箱。考虑到这一点——并且假设没有你没有提到的任何限制，例如转移中的整数水量——看起来在任何给定情况下很容易找到最佳时间表。所以试试这个最好的时间表，如果它不起作用，什么都不会。
以上不起作用，因为我忽略了约束。我当然忽略了流入和流出率，并且我还假设您可以在每个步骤中使用多个水箱，我怀疑情况可能并非如此。
还有其他方案可以解决更简单的问题 - 您可以忽略除流出率之外的所有约束，并在每个阶段以最高流出率填充水箱，并以能够满足需求的最低流出率从水箱中提供水。
这些变体不能解决您的问题，但是如果在您忽略某些约束时没有解决方案，则原始问题也无法解决。这导致了分支定界的变体。
1）如果一个简单的贪婪解决方案找到了一个好的时间表，那么这个序列显然是可以解决的。
2）尝试解决更容易的问题。如果其中任何一个无法解决，则此序列没有解决方案。
3）在第一步考虑所有可能的选择，递归调用自己来解决由此产生的较短序列，从水箱中的水开始。一旦他们中的任何一个找到解决方案，您就可以将其返回。如果您检查所有这些并且他们都说“没有解决方案”，那么就没有解决方案。