1
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.