分区问题，但有 N-k 个分区，其中 k 是参数，N 是编号。元素数

Question

以下是问题P：

输入：一组非负整数S (|S|=K), k 输出：是否存在 S 的 N-k 个分区，使得每个分区中的整数之和相等。

我的问题是 k 的值是多少，算法 P 是 P 中的吗？

例如 K=0，是微不足道的

K=1 我们只需检查 S 中是否有 N-2 个元素相等（比如等于 a），然后检查剩余元素的总和是否等于 a。

海藻糖（S）

A = 排序（S）/

a = A[1] 对于 i 在 2 到 N-2 中如果 A[i] 不等于 a 返回错误结束如果结束

如果 A[N-1] + A[N] = a 返回真别的返回错误结束

该算法的时间复杂度为O(NlogN)

但是现在当我们增加 k 时，问题就变得困难了。我想知道 K 到什么值我才能找到多项式时间算法？

我不知道如何继续。有人可以帮忙吗？

现在我知道了 NP 完全的分区问题。随着我们增加分区数量，问题变得越来越困难。 3 划分问题比划分问题更难，等等……但是为什么 N-1 划分问题有一个多项式时间算法。我知道这两个是不同的问题，但我想更好地理解这里提出的问题。

谢谢你

Answer 1

考虑最简单的暴力搜索算法，将数据分为

n-k

相等的组。

for each subset of size k:
    remove from the list
    for each way of assigning them to the list:
        check if all groups wind up the same size

有

n choose k

子集。有

(n-k)^k

作业。如果以最愚蠢的方式完成，最终检查需要时间

。

我们可以轻松地为这个愚蠢的

n^(2k+1)

实现设置上限。因此，只要

固定，这就是

中的多项式。但多项式的次数取决于

。

改进这个算法是微不足道的。我们可以及时扫描列表，并计算出所有组的大小。随着时间

O(n)

，我们可以删除所有已经是一个组的元素。如果要解决这个问题，我们最多会剩下

O(n)

个剩余元素。我们可以使用各种策略来更有效地将剩余元素转化为所需数量的组。但每个已知的策略最终都是非多项式的

2k

。

这就是你的答案。最著名的方法是

k

。非多项式位变得复杂。对于将整数分为 2 组和仅 2 组，采用众所周知的伪多项式动态规划算法。也就是说，它是

O(n + nonpolynomial(k))

和输入最大值的多项式。