9
$\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$
2
  • $\begingroup$ could you tell if there are any constraints on weights and $n$ ? $\endgroup$ Commented Aug 12, 2016 at 9:45
  • $\begingroup$ $n$ is any positive integer, and the weights are any nonnegative real numbers, just like in typical knapsack $\endgroup$
    – user57012
    Commented Aug 12, 2016 at 9:49

1 Answer 1

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$
2
  • $\begingroup$ I don't see any part where all items have the same value. $\endgroup$
    – user57012
    Commented Aug 12, 2016 at 20:01
  • $\begingroup$ In the link, take $c_i=1$ for all $i$. $\endgroup$ Commented Aug 13, 2016 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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