algorithm - 如何估计这个任务属于 NP 类？

这是我的问题：给定数字 x1，... xn。数字满足n个文件的大小和内存盘的容量 D.我们必须明白，我们能不能把文件分成3个磁盘。任何磁盘上记录的文件大小不能超过磁盘容量 D。我们估计这个计算任务属于 NP 类。在这种情况下，检查算法需要哪些额外信息（证书）？

这是我的想法，但我真的不确定：

额外信息：一组 3 组，包含 x1、...、xn 个文件。如果字符串由变量 y1,y2,y3 补充，则可以识别该集合，这些变量将放置在思想集的开头并包含一个与数字不同的符号，这样它就不会干扰文件大小字符串.

Checker：必须能够检查每组文件的总大小是否不超过D盘容量。通过引入一个变量，该算法可能很简单。变量将添加下载的文件大小，直到此数量超过 D 盘的容量或直到达到新设置的开始符号。在超过D盘容量的瞬间，发出否定响应，否则为肯定响应。该算法的耗时为 O(n)。

我不知道如何估计这个算法是 NP 类。因为 NP 可以通过非确定性图灵机在 O(n^k) 时间内求解。

标签： algorithmcomputer-sciencecomplexity-theorynpnp-complete

通俗地说，NP 的意思是“给定问题的答案，可以在多项式时间内检查答案是否正确”。您帖子中的检查算法具有复杂性 O(n)，它是多项式。因此，您的问题出在 NP 中。

注意：NP 完全问题集是 NP 的一个子集。您的问题也属于 NP 完全问题集。但是，您不需要证明这一点。在计算机科学学习的背景下，尝试这样做会暗示老师您不了解您的任务。