Consider the Unbounded Knapsack Problem (UKP): We are given a set of $n$ items $I = \{1,\ldots,n\}$ of integral weights $w_1, \ldots, w_n \in \mathbb{N}$, integral profits $p_1, \ldots, p_n \in \mathbb{N}$, and a budget $B$. The goal is to find a tuple $(x_1, \ldots, x_n) \in \mathbb{N}^n$ which maximizes the total profit $\sum_{i \in I} x_i \cdot p_i$ such that $\sum_{i \in I} x_i \cdot w_i \leq B$. In other words, in comparison to the classic knapsack, each item $𝑖$ can be taken any number of times.

Question: Suppose that the profits are all polynomial in $n$; that is, $\forall i \in I: p_i \leq poly(n)$. Now, for arbitrary parameter $n$, is there any UKP instance where the optimum must take each item exactly once? (profits being polynomial and weights can be defined arbitrarily) Stated alternatively, the profit of any feasible solution which differs from taking each item once has a strictly smaller profit.

If the answer to the above question is negative: If we construct an instance that maximizes the number of distinct items that must be taken for the optimum (w.r.t. some $n$ and again polynomial profits), what would this number be?

  • $\begingroup$ This seems like a nice homework exercise. Can you explain the context in which the problem arises, and what you know so far (relevant literature, and what you have tried that hasn't resolved the question)? $\endgroup$
    – Neal Young
    Commented Nov 7, 2022 at 15:52
  • $\begingroup$ Hey sorry for the late reply. I do not know much about this question, and not sure If the answer is affirmative. Would it be if there is a constant bound on the number of times that each item can be taken? $\endgroup$
    – John
    Commented Dec 21, 2022 at 20:06


Your Answer

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