arrays - 找到分离数组的方法，使每个子数组的总和小于或等于一个数字

Question

我这里有一个数学/算法问题。

给定一个数字数组，找到一种方法将它分成 5 个子数组，使每个子数组的总和小于或等于给定的数字。初始数组中的所有数字都必须进入子数组之一，并且是一个总和的一部分。

所以算法的输入是:d - 表示每个子数组总和必须小于或等于的数字A - 表示将被分成不同子数组的数字数组，并且将成为一个总和的一部分

算法复杂度必须是多项式。谢谢。

Answer 1

如果“子数组”是指“子集”而不是“连续切片”，则不可能找到解决此问题的多项式时间算法(除非 P = NP)。 Partition Problem是将数字列表划分为多个集合，使得两个集合的总和相等。已知它是 NP 完全的。分区问题可以简化为您的问题，如下所示:

假设 x1, ..., x_n 是正数，您希望将它们分成 2 个集合，使它们的总和相等。设 d 为这个公共(public)总和(即 xi 的总和除以 2)。通过添加 d 的三个副本，将 x_i 扩展为大小为 n+3 的数组 A。显然，将 A 划分为 5 个子数组以使每个子数组的总和小于或等于 d 的唯一方法是，如果每个子数组的总和实际上等于 d。这又需要 3 个子数组的长度为 1，每个子数组由数字 d 组成。剩下的 2 个子数组正好是原始 n 个数的一个分区。

另一方面，如果对数字和/或子数组需要的内容有额外的限制，则可能有多项式解。但是，如果是这样，您应该清楚地说明限制是什么。