algorithm - 最高的一堆盒子(算法)

Question

这个任务我有很大的问题:

你有 n (n <= 1000) 个盒子。他们每个人都有一定的力量和重量。箱子的强度是您可以放在这个箱子上的箱子的最大重量。你可以用这个盒子做的最大堆高是多少？

换句话说，如果我有一个盒子 (x1, y1), (x2, y2), .. , (xk, yk)，其中 x_i 是盒子的强度，当且仅当:

x2 >= y1

x3 >= y1+y2

...

xk >= y1+y2+...+y_(k-1)

你知道如何解决吗？我听说我们必须对这些盒子进行排序，这样如果我们可以用盒子 (a1, a2, ... ak) 做一堆，那么总是 a1 < a2 < ... < ak。我明白了，如果我们对这些框进行排序，我们可以通过简单的动态编程找到答案。但正如我所说，我不知道如何排序:\提前致谢。

Answer 1

这是一个改编自 A* 方法的想法。但是，我们不是要找到最小长度路径，而是要找到最大高度的桩。

让我们从一些理论分析开始。考虑一下，我们已经有一堆强度为 s1 的东西，我们在上面放了另一个盒子，重量为 w2，强度为 s2。生成的桩的强度将为 min(s1 - w2, s2)。

我们从一个空桩状态开始(height, strength, boxes) = (0, infinity, empty)。此外，对于任何堆状态，我们需要一个上限，我们可以在该堆上放置多少个盒子。计算此界限的一种方法是使用堆的强度与最小箱子重量(不在该堆上的箱子的重量)的商。要有效地计算此启发式算法，最初可能需要按权重对框进行排序。

剩下的就是A*算法的简单应用。从可用集中的所有状态中，选择具有最高预期堆的状态(= 高度 + 启发式)。如果这堆比你目前最高的那堆高，保存这个状态。计算尚未在堆上的每个盒子的结果堆状态，并从可用集中删除当前状态。然后迭代。

如果可用集合中没有任何桩状态的预期桩高度高于当前最高桩，则您找到了最高桩。

这种方法可以让您忽略显然不能尽早贡献最高堆的堆状态。由于一个桩状态只能从另一个桩状态到达，因此您不需要处理开放和封闭列表中的状态。