algorithm - Knapsack NP-Complete 的变体是否完整？

Question

在背包问题中，唯一的约束是拣选物品的总大小不大于包裹的总大小。我们知道背包问题是 NP 完全问题。

但是，如果我们有另一个选择固定数量项目的约束，那么这个问题仍然是 NP-Complete 吗？问题的正式描述如下所示，

最大化 $\sum_{j=1}^n p_j x_j$

st $\sum_{j=1}^n w_j x_j < W$

      $\sum_{j=1}^n x_j = N$

      $x_j = \{0,1\}$     

这是我研究中的一个公式化问题，我不确定它是否是 NP-Complete 的。请帮我。谢谢！

Answer 1

您可以通过迭代对象N集中的所有大小组合来解决受限问题。n组合数不超过n^N：

C = n! / (N! (n-N)!)
 <= n! / (n-N)!                // since N! >= 1
  = n * (n-1) * ... * (n-N+1)  // N terms
 <= n * n * ... * n            // N terms
  = n^N

由于N是固定的，因此总体复杂度是多项式的。