algorithm - Multiset Multisum Problem：形成两个子集所需的最小元素数，每个子集总和为 k 或更多

Question

我得到了一个数组（最好说是一个多重集），比如说 L。现在，我需要告诉从这个集中形成两个子集（多重集）所需的最小元素数（L），使得两个子集的每一个元素至少为 k（给定整数）。

我想到的基本想法是：最初，我们有两个空数组/集合。首先，将最大的元素添加到其中一个中。现在，从第二大开始，我将一个元素添加到两个元素中总和最小的子集中，然后继续直到我在这两个中得到至少 k 的总和。这个解决方案在许多测试用例中都有效，但后来我找到了一个反例，证明这个解决方案是不正确的。反例是：取L=[1, 2, 4, 5, 6, 7, 8]，k=16。

我知道这个问题在某种程度上是子集和问题的修改（更好地说，高级）版本，但不知道如何做到这一点。有人可以帮忙吗？

标签： algorithmsubset-sum

Answer 1

很明显，我们想从 L 的最大元素构建两个子集，所以让我们假设 L 是按降序排序的。

那么问题就变成了找到最小的 n，使得 L[0:n] 可以分成两个值 k 或更多的子集。

这等效于找到最小的 n 使得 S=L[0:n] 可以拆分为 k 和 sum(S)-k 之间的单个值子集（因为如果这样，另一个子集将自动具有 k 或更大的值是真的）。

因此，您可以运行标准的子集和算法，以递减的大小插入 L 的元素，并在每一步检查在 k 到 sum(S)-k 范围内是否有任何解。