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.


closed as unclear what you're asking by D.W., David Richerby, Rick Decker, Luke Mathieson, Wandering Logic Dec 2 '14 at 15:13

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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