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
    Nov 7 at 15:52


Your Answer

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