# 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.

• 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
Aug 8, 2020 at 15:28
• Thanks. Good point. I made the clarifications.
– Ivy
Aug 9, 2020 at 6:36
• It may be worth checking the following book on knapsack. springer.com/gp/book/9783540402862 Aug 9, 2020 at 15:38

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.