<p>The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm.</p>
<p><strong>Theorem 1.</strong> <em>For unbounded Knapsack with integer profits <span class="math-container">$(p_1,\ldots,p_n)$</span>, there is an algorithm running in time polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\max_i p_i$</span>.</em></p>
<p><em>Proof.</em> We first observe that the problem reduces in polynomial time to  the &quot;flipped&quot; variant, where the profits are given a threshold, rather than the weights:</p>
<p><strong>input:</strong> <em>weights <span class="math-container">$w=(w_1,\ldots,w_n)$</span>, positive integer profits <span class="math-container">$p=(p_1,\ldots, p_n)$</span>, and desired profit <span class="math-container">$P$</span></em><br />
<strong>output:</strong> <em>the minimum sufficient weight <span class="math-container">$W^* = \min\big\{ w\cdot x : p\cdot x \ge P,\, x\in\mathbb N_0^n\big\}$</span>.</em></p>
<p>Throughout &quot;<span class="math-container">$\cdot$</span>&quot; denotes the dot product, <span class="math-container">$a\cdot b = \sum_{i=1}^n a_i b_i$</span>.</p>
<p><strong>Lemma 1.</strong> <em>Knapsack with integer profits reduces in time polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\log(\max_i p_i)$</span> to the &quot;flipped&quot; problem defined above.</em></p>
<p>The proof of Lemma 1 is straightforward.  I've appended it at the end.</p>
<p>Next we observe that the flipped problem has an algorithm whose run-time is polynomial in <span class="math-container">$n$</span> and the profit threshold <span class="math-container">$P$</span>.</p>
<p><strong>Lemma 2.</strong> <em>There is an algorithm for the flipped problem that runs in time polynomial in <span class="math-container">$n$</span> and <span class="math-container">$P$</span>.</em></p>
<p>The proof of Lemma 2 is a standard exercise in dynamic programming.  I've appended it at the end.</p>
<p>The theorem doesn't follow directly, because the desired profit <span class="math-container">$P$</span> is not, in general, polynomial in the maximum item profit <span class="math-container">$\max_i p_i$</span>.</p>
<p>Next we develop an algorithm that runs in time polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\max_i p_i$</span>.</p>
<p>Fix any instance <span class="math-container">$(p, w, P)$</span> of the flipped variant.</p>
<p>Let <span class="math-container">$i^*=\arg\max_i p_i/w_i$</span> be the item with highest profit-to-weight ratio.</p>
<p>The key observation is the following:</p>
<p><strong>Lemma 3.</strong> <em>There is an optimal solution <span class="math-container">$x$</span> with <span class="math-container">$x_i &lt; p_{i^*}$</span> for all <span class="math-container">$i\ne i^*$</span>.</em></p>
<p><em>Proof.</em> Consider any optimal solution <span class="math-container">$x$</span>.  Suppose <span class="math-container">$x_i \ge p_{i^*}$</span> for some <span class="math-container">$i\ne i^*$</span>.  Then replace <span class="math-container">$p_{i^*}$</span> copies of item <span class="math-container">$i$</span> with <span class="math-container">$p_i$</span> copies of item <span class="math-container">$i^*$</span>.  This preserves the total profit, and cannot increase the weight.  Repeat as necessary with other items to obtain the claimed solution. <span class="math-container">$~~\Box$</span></p>
<p>In the optimal solution <span class="math-container">$x$</span> from Lemma 3, the total profit from items
other than <span class="math-container">$i^*$</span> is at most <span class="math-container">$\sum_{i\ne i^*} p_{i^*} p_i \le n(\max_i p_i)^2$</span>.  That is, the total profit from items other than <span class="math-container">$i^*$</span> is polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\max_i p_i$</span>.  Intuitively, this means that we can greedily commit to taking most of the profit from <span class="math-container">$i^*$</span>, and once we do, for the remaining problem (allocating the rest of the profit), the desired profit will be polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\max_i p_i$</span>. So we can solve that remaining problem using the algorithm from Lemma 2.  Here are the details.</p>
<p>Let optW<span class="math-container">$(p, w, P)$</span> denote the minimum weight needed to make profit <span class="math-container">$P$</span>.</p>
<p><strong>Lemma 4.</strong> <em>Let <span class="math-container">$\delta = \max(0,\lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil)$</span> and <span class="math-container">$P'= P - \delta p_{i^*}$</span>.  Then
<span class="math-container">$$\text{optW}(p, w, P) = \delta w_{i^*} + \text{optW}(p, w, P').$$</span></em></p>
<p><em>Proof.</em> The optimal solution <span class="math-container">$x$</span> from Lemma 3 has <span class="math-container">$x_i &lt; p_i$</span> for <span class="math-container">$i\ne i^*$</span>. Since <span class="math-container">$\sum_i x_i p_i \ge P$</span>, it follows that
<span class="math-container">$x_{i^*}p_{i^*} \ge P - \sum_{i\ne i^*} p_i p_{i^*}$</span>,
i.e.,
<span class="math-container">$x_{i^*} \ge \lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil = \delta$</span>.
So this optimal <span class="math-container">$x$</span> must consist of an optimal solution to <span class="math-container">$(p, w, P')$</span>, plus <span class="math-container">$\delta$</span> units added to <span class="math-container">$x_{i^*}$</span>. <span class="math-container">$~~~\Box$</span></p>
<p>(A technical remark to avoid confusion: the solution to <span class="math-container">$(p, w, P')$</span> in the proof above can still use item <span class="math-container">$i^*$</span>.  However many copies of <span class="math-container">$i^*$</span> it takes, the optimal <span class="math-container">$x$</span> will take <span class="math-container">$\delta$</span> more.)</p>
<p>Lemma 4 gives the desired algorithm:</p>
<blockquote>
<ol>
<li><p>calculate <span class="math-container">$\delta$</span>, and <span class="math-container">$P'$</span> as defined in Lemma 4:<br />
<span class="math-container">$\delta = \max(0,\lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil)$</span> where     <span class="math-container">$i^* = \arg\max_i p_i/w_i$</span><br />
<span class="math-container">$P'= P - \delta p_{i^*}$</span></p>
</li>
<li><p>return optW<span class="math-container">$(p, w, P') + \delta w_{i^*}$</span>,<br />
where optW<span class="math-container">$(p, w, P')$</span> is computed using the algorithm from Lemma 2</p>
</li>
</ol>
</blockquote>
<p>Correctness of the algorithm follows from Lemma 4. By inspection and Lemma 2 the run time is polynomial in <span class="math-container">$n$</span> and <span class="math-container">$P'$</span>, with
<span class="math-container">$$\textstyle P' = P-\delta p_{i^*} \le P - (P - \sum_{i\ne i^*} p_i p_{i^*}) 
= \sum_{i\ne i^*} p_i p_{i^*} \le n(\max_i p_i)^2.$$</span>
So the time is polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\max_i p_i$</span>. <span class="math-container">$~~~\Box$</span></p>
<p><em>Proof of Lemma 1 (reduction to flipped problem).</em> Fix an instance <span class="math-container">$(p, w, W)$</span> of Knapsack with integer profits. The optimal solution has profit <span class="math-container">$P^*$</span> at most <span class="math-container">$\lambda^* = p_{i^*} W/w_{i^*}$</span>, because no item has a profit per weight ratio larger than <span class="math-container">$p_{i^*}/w_{i^*}$</span>.  On the other hand, using just item <span class="math-container">$i^*$</span>, as many items as possible, yields a solution of profit <span class="math-container">$\lfloor W/w_{i^*}\rfloor p_{i^*} &gt; \lambda^* - p_{i^*}$</span>. So <span class="math-container">$\lambda^* - p_{i^*} \le P^* \le \lambda^*.$</span>  Use binary search for <span class="math-container">$P$</span> in the range <span class="math-container">$\lambda^* - p_{i^*}$</span> to <span class="math-container">$\lambda^*$</span> (solving the flipped problem <span class="math-container">$(p, w, P)$</span> in each iteration) to find the maximum profit <span class="math-container">$P^*$</span> such that the minimum required weight to achieve profit <span class="math-container">$P^*$</span> is at most <span class="math-container">$W$</span>.  This <span class="math-container">$P^*$</span> will be the maximum profit achievable with weight-budget of <span class="math-container">$W$</span>.  The time for this reduction is polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\log(\max_i p_i)$</span>. <span class="math-container">$~~\Box$</span></p>
<p><em>Proof of Lemma 2 (standard dynamic-programming-algorithm for the flipped problem).</em> Fix an input <span class="math-container">$(p, w, P)$</span>.  For <span class="math-container">$i\in\{0,1,\ldots,n\}$</span> and <span class="math-container">$Q\in \{0,1,\ldots, P\}$</span>, define <span class="math-container">$W(i, Q)$</span> to be the minimum sufficient weight for the subproblem formed by the first <span class="math-container">$i$</span> items and desired profit <span class="math-container">$Q$</span>.
Then
<span class="math-container">$$W(i, Q) = \begin{cases}
0 &amp; \text{if } Q = 0 \\
\infty &amp; \text{if } Q&gt;0, i=0 \\
\min\big\{ x_i w_i + W(i-1, Q-x_i p_i) : x_i\in\mathbb N_0,\, x_i p_i \le Q\big\} &amp; \text{otherwise.}
\end{cases}$$</span>
There are <span class="math-container">$O(n P)$</span> subproblems, and for each the right-hand side of the recurrence can be evaluated in time <span class="math-container">$O(P)$</span>, so the dynamic-programming algorithm takes time <span class="math-container">$O(n P^2)$</span>. <span class="math-container">$~~~\Box$</span></p>
<p><em>EDIT: Looking briefly over the literature, the same idea (but for weights instead of profits) has been used for unbounded Knapsack with small weights.  See e.g. Section 8.2.1 of <a href="https://doi.org/10.1007/978-3-540-24777-7_8" rel="nofollow noreferrer">https://doi.org/10.1007/978-3-540-24777-7_8</a> or Section 10.4 of  <a href="https://doi.org/10.1007/978-3-540-76796-1_10" rel="nofollow noreferrer">https://doi.org/10.1007/978-3-540-76796-1_10</a>. I don't know whether it has also been used before for profits.</em></p>

CC BY-SA 4.0
2020-08-18T15:36:23.273Z
2020-08-20T15:04:33.037Z
2020-08-20T15:04:33.037Z
Neal Young
<p>Consider the <em>unbounded</em> Knapsack problem where we are given <span class="math-container">$n$</span> items of integral weights <span class="math-container">$w_i$</span>, integral profits <span class="math-container">$p_i$</span>, and a max weight <span class="math-container">$W$</span>. The goal is to maximize the total profit <span class="math-container">$\sum_i x_ip_i$</span> subject to the total weight <span class="math-container">$\sum_i w_i x_i$</span> being at most <span class="math-container">$W$</span>.  Here (in the unbounded variant) each item <span class="math-container">$i$</span> can be taken any number of times, so each <span class="math-container">$x_i$</span> can take any value in <span class="math-container">$\mathbb N_0$</span>.</p>
<p>In general, this problem is NP-hard, but I am wondering about the restriction to instances with <em>small profits</em> --- where every item profit <span class="math-container">$p_i$</span> is <span class="math-container">$O(n)$</span>.  With this restriction, is the unbounded Knapsack problem NP-hard, or is there a poly-time algorithm for it?</p>
<p>For comparison, consider the standard Knapsack problem, where each item can be taken at most once, so each <span class="math-container">$x_i$</span> is either 0 or 1.  This version is NP-hard by reduction from Subset Sum. (That reduction creates profits that are the same as the weights, and both are exponential.)  But for instances where each item profit is <span class="math-container">$O(n)$</span>, the maximum achievable profit <span class="math-container">$P$</span> is <span class="math-container">$O(n^2)$</span>, and there is a standard dynamic-programming algorithm that runs in time polynomial in <span class="math-container">$n$</span> and <span class="math-container">$P$</span>, so the run-time in the case of small profits is polynomial in <span class="math-container">$n$</span>. In contrast, for the unbounded problem, even with small profits, the maximum achievable profit is not in general polynomial in <span class="math-container">$n$</span>, so the same approach does not yield a polynomial-time algorithm.</p>

CC BY-SA 4.0
2020-08-08T15:28:41.360Z
In the unbounded version where you can take a single item as many times as possible, even though each individual profit has order $n$, the total possible max profit might be huge due to $W$. I was wondering if dynamic programming still work here?
Ivy
CC BY-SA 4.0
2020-08-09T06:36:18.383Z
Thanks. Good point. I made the clarifications.
Ivy
CC BY-SA 4.0
2020-08-09T15:38:48.200Z
It may be worth checking the following book on knapsack. https://www.springer.com/gp/book/9783540402862
Chandra Chekuri
<np-hardness><reductions><np><dynamic-programming>
Is the knapsack variant with small profit and unlimited repetition of items NP-hard?
Ivy
# Is the knapsack variant with small profit and unlimited repetition of items NP-hard?

(Asked by: username_0 on 2020-08-04)

Consider the *unbounded* Knapsack problem where we are given $n$ items of integral weights $w\_i$, integral profits $p\_i$, and a max weight $W$. The goal is to maximize the total profit $\sum\_i x\_ip\_i$ subject to the total weight $\sum\_i w\_i x\_i$ being at most $W$. Here (in the unbounded variant) each item $i$ can be taken any number of times, so each $x\_i$ can take any value in $\mathbb N\_0$.

In general, this problem is NP-hard, but I am wondering about the restriction to instances with *small profits* --- where every item profit $p\_i$ is $O(n)$. With this restriction, is the unbounded Knapsack problem NP-hard, or is there a poly-time algorithm for it?

For comparison, consider the standard Knapsack problem, where each item can be taken at most once, so each $x\_i$ is either 0 or 1. This version is NP-hard by reduction from Subset Sum. (That reduction creates profits that are the same as the weights, and both are exponential.) But for instances where each item profit is $O(n)$, the maximum achievable profit $P$ is $O(n^2)$, and there is a standard dynamic-programming algorithm that runs in time polynomial in $n$ and $P$, so the run-time in the case of small profits is polynomial in $n$. In contrast, for the unbounded problem, even with small profits, the maximum achievable profit is not in general polynomial in $n$, so the same approach does not yield a polynomial-time algorithm.

**Tags:** np-hardness, reductions, np, dynamic-programming
> **Comments:**
> **username_0**: In the unbounded version where you can take a single item as many times as possible, even though each individual profit has order $n$, the total possible max profit might be huge due to $W$. I was wondering if dynamic programming still work here?  
> **username_0**: Thanks. Good point. I made the clarifications.  
> **username_1**: It may be worth checking the following book on knapsack. https://www.springer.com/gp/book/9783540402862  

---

## 1 answers

### Answer by username_2 on 2020-08-18. Score: 3

The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm.

**Theorem 1.** *For unbounded Knapsack with integer profits $(p\_1,\ldots,p\_n)$, there is an algorithm running in time polynomial in $n$ and $\max\_i p\_i$.*

*Proof.* We first observe that the problem reduces in polynomial time to the "flipped" variant, where the profits are given a threshold, rather than the weights:

**input:** *weights $w=(w\_1,\ldots,w\_n)$, positive integer profits $p=(p\_1,\ldots, p\_n)$, and desired profit $P$*  
**output:** *the minimum sufficient weight $W^\* = \min\big\{ w\cdot x : p\cdot x \ge P,\, x\in\mathbb N\_0^n\big\}$.*

Throughout "$\cdot$" denotes the dot product, $a\cdot b = \sum\_{i=1}^n a\_i b\_i$.

**Lemma 1.** *Knapsack with integer profits reduces in time polynomial in $n$ and $\log(\max\_i p\_i)$ to the "flipped" problem defined above.*

The proof of Lemma 1 is straightforward. I've appended it at the end.

Next we observe that the flipped problem has an algorithm whose run-time is polynomial in $n$ and the profit threshold $P$.

**Lemma 2.** *There is an algorithm for the flipped problem that runs in time polynomial in $n$ and $P$.*

The proof of Lemma 2 is a standard exercise in dynamic programming. I've appended it at the end.

The theorem doesn't follow directly, because the desired profit $P$ is not, in general, polynomial in the maximum item profit $\max\_i p\_i$.

Next we develop an algorithm that runs in time polynomial in $n$ and $\max\_i p\_i$.

Fix any instance $(p, w, P)$ of the flipped variant.

Let $i^\*=\arg\max\_i p\_i/w\_i$ be the item with highest profit-to-weight ratio.

The key observation is the following:

**Lemma 3.** *There is an optimal solution $x$ with $x\_i < p\_{i^\*}$ for all $i\ne i^\*$.*

*Proof.* Consider any optimal solution $x$. Suppose $x\_i \ge p\_{i^\*}$ for some $i\ne i^\*$. Then replace $p\_{i^\*}$ copies of item $i$ with $p\_i$ copies of item $i^\*$. This preserves the total profit, and cannot increase the weight. Repeat as necessary with other items to obtain the claimed solution. $~~\Box$

In the optimal solution $x$ from Lemma 3, the total profit from items
other than $i^\*$ is at most $\sum\_{i\ne i^\*} p\_{i^\*} p\_i \le n(\max\_i p\_i)^2$. That is, the total profit from items other than $i^\*$ is polynomial in $n$ and $\max\_i p\_i$. Intuitively, this means that we can greedily commit to taking most of the profit from $i^\*$, and once we do, for the remaining problem (allocating the rest of the profit), the desired profit will be polynomial in $n$ and $\max\_i p\_i$. So we can solve that remaining problem using the algorithm from Lemma 2. Here are the details.

Let optW$(p, w, P)$ denote the minimum weight needed to make profit $P$.

**Lemma 4.** *Let $\delta = \max(0,\lceil P/p\_{i^\*} - \sum\_{i\ne i^\*} p\_i \rceil)$ and $P'= P - \delta p\_{i^\*}$. Then
$$\text{optW}(p, w, P) = \delta w\_{i^\*} + \text{optW}(p, w, P').$$*

*Proof.* The optimal solution $x$ from Lemma 3 has $x\_i < p\_i$ for $i\ne i^\*$. Since $\sum\_i x\_i p\_i \ge P$, it follows that
$x\_{i^\*}p\_{i^\*} \ge P - \sum\_{i\ne i^\*} p\_i p\_{i^\*}$,
i.e.,
$x\_{i^\*} \ge \lceil P/p\_{i^\*} - \sum\_{i\ne i^\*} p\_i \rceil = \delta$.
So this optimal $x$ must consist of an optimal solution to $(p, w, P')$, plus $\delta$ units added to $x\_{i^\*}$. $~~~\Box$

(A technical remark to avoid confusion: the solution to $(p, w, P')$ in the proof above can still use item $i^\*$. However many copies of $i^\*$ it takes, the optimal $x$ will take $\delta$ more.)

Lemma 4 gives the desired algorithm:

> 1. calculate $\delta$, and $P'$ as defined in Lemma 4:  
>    $\delta = \max(0,\lceil P/p\_{i^\*} - \sum\_{i\ne i^\*} p\_i \rceil)$ where $i^\* = \arg\max\_i p\_i/w\_i$  
>    $P'= P - \delta p\_{i^\*}$
> 2. return optW$(p, w, P') + \delta w\_{i^\*}$,  
>    where optW$(p, w, P')$ is computed using the algorithm from Lemma 2

Correctness of the algorithm follows from Lemma 4. By inspection and Lemma 2 the run time is polynomial in $n$ and $P'$, with
$$\textstyle P' = P-\delta p\_{i^\*} \le P - (P - \sum\_{i\ne i^\*} p\_i p\_{i^\*})
= \sum\_{i\ne i^\*} p\_i p\_{i^\*} \le n(\max\_i p\_i)^2.$$
So the time is polynomial in $n$ and $\max\_i p\_i$. $~~~\Box$

*Proof of Lemma 1 (reduction to flipped problem).* Fix an instance $(p, w, W)$ of Knapsack with integer profits. The optimal solution has profit $P^\*$ at most $\lambda^\* = p\_{i^\*} W/w\_{i^\*}$, because no item has a profit per weight ratio larger than $p\_{i^\*}/w\_{i^\*}$. On the other hand, using just item $i^\*$, as many items as possible, yields a solution of profit $\lfloor W/w\_{i^\*}\rfloor p\_{i^\*} > \lambda^\* - p\_{i^\*}$. So $\lambda^\* - p\_{i^\*} \le P^\* \le \lambda^\*.$ Use binary search for $P$ in the range $\lambda^\* - p\_{i^\*}$ to $\lambda^\*$ (solving the flipped problem $(p, w, P)$ in each iteration) to find the maximum profit $P^\*$ such that the minimum required weight to achieve profit $P^\*$ is at most $W$. This $P^\*$ will be the maximum profit achievable with weight-budget of $W$. The time for this reduction is polynomial in $n$ and $\log(\max\_i p\_i)$. $~~\Box$

*Proof of Lemma 2 (standard dynamic-programming-algorithm for the flipped problem).* Fix an input $(p, w, P)$. For $i\in\{0,1,\ldots,n\}$ and $Q\in \{0,1,\ldots, P\}$, define $W(i, Q)$ to be the minimum sufficient weight for the subproblem formed by the first $i$ items and desired profit $Q$.
Then
$$W(i, Q) = \begin{cases}
0 & \text{if } Q = 0 \\
\infty & \text{if } Q>0, i=0 \\
\min\big\{ x\_i w\_i + W(i-1, Q-x\_i p\_i) : x\_i\in\mathbb N\_0,\, x\_i p\_i \le Q\big\} & \text{otherwise.}
\end{cases}$$
There are $O(n P)$ subproblems, and for each the right-hand side of the recurrence can be evaluated in time $O(P)$, so the dynamic-programming algorithm takes time $O(n P^2)$. $~~~\Box$

*EDIT: Looking briefly over the literature, the same idea (but for weights instead of profits) has been used for unbounded Knapsack with small weights. See e.g. Section 8.2.1 of <https://doi.org/10.1007/978-3-540-24777-7_8> or Section 10.4 of <https://doi.org/10.1007/978-3-540-76796-1_10>. I don't know whether it has also been used before for profits.*


---

