我必须证明以下问题是NP-Complete，需要一些有用的提示来说明如何继续。
问题：
我们正在寻找会议预订系统。输入是可能时间的列表n以及m个列表（其中m <= n），每个人一个列表包含他们可能的会议时间的选择。对于每个可能的时间，还给出优先级编号。对于n列表中的每个预约时间，还给出了成本。 （预订房间的费用）。该算法应分配时间，以便已预订的人的组合优先级应尽可能小，而预订的总费用不应高于M.
NP
所以首先要表明它在NP中我们应该表明，给定一个正确的解决方案，可以证实它确实是正确的。我想它应该验证成本是否低于K的阈值，并且正确解决方案的优先级确实是最小的 - 这两者都可以在我假设的多项式时间内完成。我们遍历人员列表，声称每个人都有时间给他们，在变量中加上成本，并在此列表的末尾断言成本低于K.优先级可以类似的方式处理我想？
NP Hard
然后展示它的NP Hard我可以使用背包问题，因为它们非常相似。使用输入S，包的大小，具有权重w和值v的项目列表以及作为目标值的目标W.我想很清楚，S可以与成本相关联，W与优先级相关吗？因此我们希望S的大小低于S，即我们对上述问题的条件类似，其中成本必须低于K.那么W，总值通常应该超过W，但在我们的例子中我们希望它尽可能低，这似乎可行。
我担心在验证问题时我可能会采取错误的方式。此外，显示它的NP Hard的减少也许并没有被全部考虑过。一些指针会非常有用！谢谢
NP
当您在NP中证明问题时，您必须首先将问题转化为决策问题。然后，您可以在开始描述的多项式时间内验证证书。
NP Hard
您需要将背包问题转换为会议问题。你是正确的方式，因为你正在将背包的大小和重量转化为会议问题。一旦找出转换，就必须验证它是否可以在多项式时间内完成。最后，您可以证明Knapsack的解决方案是解决问题的解决方案，反之亦然。