找到最小数 N 以在总和低于 N 的 X 子集中划分堆栈值的算法

Question

我有一个包含整数值对象的堆栈。我想买一辆容量为 N(N 未知)的卡车，以确保我可以在最大 X 圈内运输所有物体。

X 是已知的。换句话说，我必须在总和低于 N 的最大 X 个子集中划分堆栈(必须保持对象的顺序)并找到最小 N。

你能帮我提供一个算法或想法吗？谢谢。

Answer 1

如果，如您所述，“必须保持对象的顺序”，那么我们可以通过对 N 进行二进制搜索来解决此问题，在 O(|objects| * log m )，其中 m 是总和。

如果可以重新排列对象的顺序，@hlt 在评论中链接到的关于多路数字分区的论文将适用。在这种情况下，顺序是固定的，我们可以尝试不同的 N，尽可能多地打包分区。如果我们选择的 N 太小，我们最终会超过 X。这使得 N 有序，因此可搜索。