Is the knapsack variant with small profit and unlimited repetition of items NP-hard? 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.
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 &quot;flipped&quot; 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 &quot;$\cdot$&quot; 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 &quot;flipped&quot; 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 &lt; 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 &lt; 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:


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^*}$

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^*} &gt; \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 &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}$$
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.