1
$\begingroup$

Is there any literature about the complexity of the integer knapsack problem with bounded weights? To make it clear, I want an optimal solution to the following problem:

$\max \sum_{i=1}^k c_i \cdot x_i$

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

$x_i \in \{0,\ldots,k_i\}$

where $k_i$ is an item-specific limit for the number of copies that can be taken of item $i$ and $w_i$ is integral but bounded by $k$.

I'm not sure whether it is NP-hard or not...in contrast to the "traditional" knapsack problem, it would be possible to iterate over $w_i$ here (in polynomial time), but not to iterate over the whole sum since the values $k_i$ are not bounded by a polynomial. On the other hand, I cannot imagine a reduction of an $NP$-hard problem. Any ideas?

$\endgroup$
  • 2
    $\begingroup$ Sounds to me like the dynamic programming solution for knapsack is applicable in your case. en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming $\endgroup$ – A.Schulz Mar 4 '14 at 15:01
  • $\begingroup$ Probably, yes. But unfortunately that doesn't tell me whether the problem is (weakly) $NP$-hard or not... $\endgroup$ – user1742364 Mar 4 '14 at 15:11
  • $\begingroup$ Any ideas or clues? $\endgroup$ – user1742364 Mar 13 '14 at 9:53

Your Answer

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

Browse other questions tagged or ask your own question.