6
$\begingroup$

I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight constraints.

Maximize $\sum_{j=1}^nx_j$

subject to $\sum_{j=1}^nw_{ij}x_j\leq W_i$ for $1\leq i\leq m$

and $x_i=0,1$.

This is a special case of multidimensional knapsack. I've looked at the list of knapsack problems, but the only one with uniform value is not multidimensional but instead wants the sum of weights to be exactly $W$. Is there some reference for the version I described?

$\endgroup$
  • $\begingroup$ could you tell if there are any constraints on weights and $n$ ? $\endgroup$ – sashas Aug 12 '16 at 9:45
  • $\begingroup$ $n$ is any positive integer, and the weights are any nonnegative real numbers, just like in typical knapsack $\endgroup$ – user57012 Aug 12 '16 at 9:49
1
$\begingroup$

Your problem appears to be a special case of integer programming where the variables are boolean. I could not find it on wikipedia, but a lot of course materials online introduce this problem as Capital Budgeting problem under different models of integer programming. Hope it helps.

$\endgroup$
  • $\begingroup$ I don't see any part where all items have the same value. $\endgroup$ – user57012 Aug 12 '16 at 20:01
  • $\begingroup$ In the link, take $c_i=1$ for all $i$. $\endgroup$ – sashas Aug 13 '16 at 6:52

Your Answer

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

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