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.

  • $\begingroup$ You haven't told us what is fixed (what are the inputs) and what we're allowed to choose (what is the desired output). Are the $v_i,w_i$'s constants that are provided in the input? $W$? $B$? $r$? Also, I think your first step should be to figure out how $r$ depends on $v_i,w_i$, and then ask about a specific instance. $\endgroup$ – D.W. Nov 28 '14 at 9:24

$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$.

  • $\begingroup$ No, it is not a constant, because $r$ is a variable. (Let me clarify that $r$ in particular varies with the values of $w_i$ and $v_i$, though I cannot tell in what way.) I think you gave some other answer first? $\endgroup$ – sr3u Nov 26 '14 at 10:13
  • $\begingroup$ I initially misread the problem statement. For a particular instance of the problem (fixed $v_i$ and $w_i$), $r$ is constant so we may disregard the term $B\frac{W}{r}$ when solving the problem. Or does $r$ somehow depend on $x_i$ as well? $\endgroup$ – Tom van der Zanden Nov 26 '14 at 10:16
  • $\begingroup$ Yes, that is a degenerate case, but if we have to choose the values of the variables the simplification does not apply, and this is where the problem lies. $\endgroup$ – sr3u Nov 26 '14 at 10:19
  • 1
    $\begingroup$ So exactly what values are you trying to solve for? Since you stated this is a knapsack problem, I assumed $v_i$ (the values) and $w_i$ (the weights) were part of the problem input, and you were trying to solve for $x_i$ (a binary variable indicating whether to take item $i$ or not) and that $r$ depended on the values of $w_i$ and $v_i$. Since $w_i$ and $v_i$ are part of the input, isn't $r$ decided at the time the input is given, and the term is thus constant for any particular instance of the problem? $\endgroup$ – Tom van der Zanden Nov 26 '14 at 10:21
  • $\begingroup$ Yes, I believe you're right. Thanks. I may have other related queries (re more varieties of knapsack) later. $\endgroup$ – sr3u Nov 26 '14 at 11:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.