algorithm - 预订系统是 NP Complete

Question

我必须证明以下问题是 NP 完全问题，并且需要一些有关如何继续的有用提示。

问题:

我们正在研究 session 预订系统。输入是 n 个可能时间的列表以及 m 个列表(其中 m <= n)，每个人一个列表，其中包含他们选择的可能 session 时间。对于每个可能的时间，还会给出一个优先级编号。对于 n 列表中的每个预订时间，还给出了成本。 (预订房间的费用)。算法应该分配时间，使得已预订者的组合优先级应尽可能小，而预订的总成本不应高于 M。

NP

所以首先要证明它在 NP 中，我们应该证明给定一个正确的解决方案，可以验证它确实是正确的。我想它应该验证成本低于 K 的阈值并且正确解决方案的优先级确实是最小的 - 这两者都可以在我假设的多项式时间内完成。我们遍历人员列表，断言每个人都有一个时间，将成本加到一个变量中，并在该列表的末尾断言成本低于 K。优先级可以用类似的方式处理我想？

NP 困难

然后为了证明它是 NP Hard，我可以使用背包问题，因为它们非常相似。输入 S、包的大小、重量为 w 和值(value)为 v 的项目列表以及目标 W，即目标值。我想很明显 S 可以与成本相关，而 W 可以与优先级相关？所以我们希望 S(大小)低于 S，即对于上述问题，我们有类似的条件，成本必须低于 K。那么 W，总值(value)通常应该超过 W，但在我们的例子中，我们希望它尽可能低，这似乎是可行的。

恐怕我在验证问题时走错了路。此外，减少显示它是 NP 硬的可能并不是所有的考虑。一些指示会非常有帮助!谢谢

Answer 1

NP

当你要证明问题是 NP 问题时，你必须先把你的问题变成一个决策问题。然后您可以在开始描述时以多项式时间验证您的证书。

NP 困难

您需要将背包问题转化为 session 问题。你走的路是对的，因为你正在将背包的大小和重量转化为 session 问题。计算出转换后，您必须验证它是否可以在多项式时间内完成。最后，您可以证明背包问题的解决方案是 session 问题的解决方案，反之亦然。