Is the variation of Knapsack NP-Complete?

Question

In the knapsack problem, the only constraint is that the total size of picked items is no larger than the total size of the package. We know the Knapsack problem is NP-Complete.

However, if we have another constraint of choosing fixed number of items, is this problem still NP-Complete? The formal description of the problem is shown as follows,

Maximize $\sum_{j=1}^n p_j x_j$

s.t. $\sum_{j=1}^n w_j x_j < W$

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

      $x_j = \{0,1\}$     

This is a formulated problem in my research and I am not sure whether it is NP-Complete or not. Please help me. Thanks!

Answer 1

You can solve the constrained problem by iterating over all combinations of size N from your set of n objects. The number of combinations is no more than 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

Since N is fixed, the overall complexity is therefore polynomial.