I am trying to know whether the following problem is NP-hard:

Input: A positive number $k$ and $N$ pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$.

The problem is to select a subset of numbers $S$ among the set $\{a_1,b_1,a_2,b_2,..., a_N, b_N\}$ such that it maximizes the sum of the values of the $S$.

The are two constraints:

  1. For each pair $i,\; (i=1,...,N)$ you cannot select $a_i \text{ AND } b_i$ (either $a_i$, or $b_i$, or none, but never both)

  2. The weight of selecting the number $a_i$ is 1, and the weight of selecting the number $b_i$ is 2 (for all $i=1,...,N$). The sum of the weights of all the numbers selected in $S$ cannot exceed $k$.

Is this problem NP-hard?

  • $\begingroup$ en.wikipedia.org/wiki/Dynamic_programming​ ​ ​ $\endgroup$ – user12859 Nov 19 '15 at 6:44
  • $\begingroup$ @RickyDemer Sure, that's the approach to solving this kind of problem but it says nothing about whether it's NP-hard. However, ordinary knapsack is NP-hard and can be solved in only pseudopolynomial time using dynamic programming. $\endgroup$ – David Richerby Nov 19 '15 at 10:37
  • 2
    $\begingroup$ It's polynomial-time solvable. A tip: you can use a greedy approach (so a little bit more stronger approach than the "generic" DP suggested by Ricky Demer); if the "initial" total weight $k_1 = 2$ then you can calculate the max sum. Increasing the total allowed weight $k_2 = 4, k_3 = 6, ...,k_j = 2*j, ... , k_j = k$ can only increase the previous max sum and at every "step" you must only decide to include a new $b_i$ or two new $a_i,a_{i'}$ ... $\endgroup$ – Vor Nov 19 '15 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.