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$
3
  • 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, 2014 at 15:01
  • $\begingroup$ Probably, yes. But unfortunately that doesn't tell me whether the problem is (weakly) $NP$-hard or not... $\endgroup$ Mar 4, 2014 at 15:11
  • $\begingroup$ Any ideas or clues? $\endgroup$ Mar 13, 2014 at 9:53

0

Your Answer

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

Browse other questions tagged or ask your own question.