World's most popular travel blog for travel bloggers.

Extended knapsack: is it NP-complete?

, , No Comments
Problem Detail: 

I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same:

Maximize the value of

($\sum_{i=1}^n v_i \cdot x_i) + B \cdot \frac{W}{r}$

subject to

$ \sum_{i=1}^n w_i \cdot x_i \leq W$.

Here, $W$ and $B$ are constants, and $r$ is an integer variable with $1 \leq r \leq n$, whose behavior vis-à-vis the variables $v_i$ and $w_i$ is unknown to me.

It is obvious that if $B$ is 0, this reduces to the classical knapsack and is hence NP-complete, but is it still NP-complete otherwise? Can we say anything about this problem considering possible behaviors of $r$?

It's been a while since I studied algorithms; please bear with me if this looks too simple (let me clarify that this question arose from research; I'm not a kid trying to cheat on homework). I have also not found an answer in the responses to other knapsack questions asked on this forum.

Asked By : sr3u
Answered By : Tom van der Zanden

$B*\frac{W}{r}$ is a constant, so adding it to your objective function has no effect on the solution. The problem is NP-complete, regardless of the values of $B$ and $r$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback