Suppose I have $N$ items with non-negative weights $w_1, \dots, w_N \geq 0$ and non-negative value $v_1, \dots, v_N \geq 0$.
The knapsack problem is to choose a subset $I \subseteq \{1,\dots,N\}$ such that
- $\sum_{i \in I} w_i \leq B$
- $\sum_{i \in I} v_i$ maximal,
where $B$ is an upper bound for the weight. In other words, I want to pack as much value into my knapsack as I can but keep the weight below $B$.
What about the following combinatorial problem: choose a subset $I \subseteq \{1,\dots,N\}$ such that
- $\sum_{i \in I} w_i$ minimal
- $\sum_{i \in I} v_i \geq C$,
where $C$ is a lower bound for the value. In other words, I want to pack as least weight into my knapsack as I can but keep the value above $C$.
Question: are these two problems equivalent? Can I easily reformulate one in terms of the other? Note that weights and values need to be non-negative.
Best Answer
The first problem is, \begin{align} \max_s&\quad s^{T}v \\ s.t.&\quad s^Tw \leq B \\ &\quad s\in \{0,1\}^{N} \end{align} where $s = (s_1,s_2,\dots,s_N)$ is a vector that selects the $i$th item if $s_i=1$ and doesn't select the item if $s_i = 0$.
The second problem is, \begin{align} \min_\bar{s}&\quad \bar{s}^{T}\bar{w} \\ s.t.&\quad \bar{s}^T\bar{v} \geq C \\ &\quad \bar{s}\in \{0,1\}^{N} \end{align} which is equivalent to, \begin{align} \max_\bar{s}&\quad -\bar{s}^{T}\bar{w} \\ s.t.&\quad -\bar{s}^T\bar{v} \leq -C \\ &\quad \bar{s}\in \{0,1\}^{N} \end{align}
Therefore, the second problem can be formulated as a knapsack problem by setting, $-\bar{w} = v$, $-\bar{v} = w$ and $-C = B$.