<p><strong>Consider the Unbounded Knapsack Problem (UKP):</strong> We are given a set of <span class="math-container">$n$</span> items <span class="math-container">$I = \{1,\ldots,n\}$</span> of integral weights <span class="math-container">$w_1, \ldots, w_n \in \mathbb{N}$</span>, integral profits <span class="math-container">$p_1, \ldots, p_n \in \mathbb{N}$</span>, and a budget <span class="math-container">$B$</span>. The goal is to find a tuple <span class="math-container">$(x_1, \ldots, x_n) \in \mathbb{N}^n$</span> which maximizes the total profit <span class="math-container">$\sum_{i \in I} x_i \cdot p_i$</span> such that <span class="math-container">$\sum_{i \in I} x_i \cdot w_i \leq B$</span>. In other words,  in comparison to the classic knapsack, each item <span class="math-container">$$</span> can be taken any number of times.</p>
<p><strong>Question:</strong> Suppose that the profits are all polynomial in <span class="math-container">$n$</span>; that is, <span class="math-container">$\forall i \in I: p_i \leq poly(n)$</span>. Now, for arbitrary parameter <span class="math-container">$n$</span>, <strong>is there any UKP instance where the optimum must take each item exactly once?</strong> (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.</p>
<p>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 <span class="math-container">$n$</span> and again polynomial profits), what would this number be?</p>

CC BY-SA 4.0
2022-11-07T15:52:57.040Z
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)?
Neal Young
CC BY-SA 4.0
2022-12-21T20:06:19.317Z
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?
John
<optimization><packing><subset-sum><hard-instances>
Unbounded Knapsack Instance with a Single Optimum that takes each Item Once?
John
# Unbounded Knapsack Instance with a Single Optimum that takes each Item Once?

(Asked by: username_0 on 2022-11-06)

**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?

**Tags:** optimization, packing, subset-sum, hard-instances
> **Comments:**
> **username_1**: 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)?  
> **username_0**: 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?  

---

## 0 answers

