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