Knapsack

| Tags Algorithm 

Knapsack is a very classic problem of dynamic programming. This problem can be classified by two ways, the first way to classify Knapsack into two categories according to whether the item can be partially token, and the second way to classify it into two categories according to whether the item can be repeatedly token. So there are four types of Knapsack, namely 0-1 Knapsack without repetition, 0-1 Knapsack with repetition, Knapsack without repetition and Knapsack with repetition.

0-1 Knapsack without repetition

This is the most common case of Knapsack problem. It defines as:

Let $$$ U = \{u_1, u_2, …, u_n\}$$$ be a set of items to be packed in a knapsack of size $$$C$$$. For $$$ 1 \leq j \leq n$$$, let $$$ s_j $$$ and $$$ v_j $$$ be the size and value of the j-th item.

Problem: We want to find a subset of $$$ S \subseteq U $$$ such that
$$ \sum_{u_j \in S} v_j $$
is maximized subject to the constraint
$$ \sum_{u_j \in S} s_j \leq C $$

Let V[i, j] be the value obtained by filling a knapsack of size j with items from the first i items $$$\{u_1, u_2, …, u_i\}$$$ in an optimal way.

The recurrence relation

$$ V[i,j] = \left\{ \begin{array}{11} 0 & \mbox{if $i=0$ or $j=0$} \\ V[i-1,j] & \mbox{if $j \lt s_i$ } \\ max\{V[i-1, j], V[i-1, j-s_i] + v_i\} & \mbox{if $j \geq s_i$} \end{array} \right. $$

The result is V[n, C].

0-1 Knapsack with repetition

This problem is very similar with the above one, to allow repetition we just need to add one rule that each item can repeatedly token without limitations.

Let V[j] be the value obtained by filling a knapsack of size j in an optimal way.

The recurrence relation $$ V[j] = \left\{ \begin{array}{11} 0 & \mbox{if $j=0$} \\ max\{V[j-1], V[j-s_i]+V_i : s_i \leq j \} & \mbox{if $j \gt 0$} \end{array} \right. $$

The result is V[C].

Knapsack without repetition

To Be Done

Knapsack with repetition

To Be Done


Previous     Next