The Continuous Knapsack Problem

Consider the linear program

$$\begin{array}{lrclr} \max & c^Tx \\ \mbox{subject to} & a^T... ...leq & b & \quad \quad (P) \\ & 0 \leq x & \leq & u \end{array}$$

where $c$, $a$, and $u$ are all positive $n$-vectors and $b$ is a positive scalar. Assume without loss of generality that

$$\frac{c_1}{a_1} \geq \frac{c_2}{a_2} \geq \ldots \geq \frac{c_n}{a_n}.$$

Assume $a^Tu > b$ (otherwise $x=u$ is optimal).

Let $k$ be the index satisfying

$$\sum_{i=1}^{k-1} a_i u_i < b \quad \mbox{and} \quad \sum_{i=1}^k a_iu_i \geq b$$

Let $r=b-\sum_{i=1}^{k-1} a_i u_i$. Then the optimal solution is

$$x_i = \left\{ \begin{array}{ll} u_i & i=1,\ldots,k-1 \\ \frac{r}{a_k} & i=k \\ 0 & i=k+1,\ldots,n \end{array} \right.$$

Proof:

The dual problem is

$$\begin{array}{lrcrcllr} \min & by & + & u^Tw \\ \mbox{subje... ... \quad (D) \\ & \multicolumn{3}{r}{y,w} & \geq & 0 \end{array}$$

Let $y^*=\frac{c_k}{a_k}$ and choose the slack variables $w$ as:

$$w_i = \left\{ \begin{array}{ll} c_i-a_iy & i=1,\ldots,k-1 \\ 0 & i=k,\ldots,n \end{array} \right. %\\$$

This solution is feasible, satisfies complementary slackness, and has the same value as the primal solution.