Knapsack problem

Your knapsack (or possibly your back) has the capacity to hold $C$ kilograms ($C$ is a nonnegative integer). You are presented with a collection of $n$ categories of goodies that are free for the taking, category $i$ items have weight $w_i$ and value $v_i$ (weights and values also nonnegative integers). Fill your knapsack so that you can carry off ($C$ is not exceeded) the maximum value. Since you're allowed to take more than one item of the same type, you can express your answer as a list of indices $i_1, i_2, \ldots , i_k$ such that $w_{i_1} + \cdots + w_{i_k}$ $\leq$ $C$, and you maximize $v_{i_1} + \cdots + v_{i_k}$.

Here's an example you may be able to solve without any high-powered algorithm. Suppose $C$ = 11, $w_1 = 3$, $w_2 = 4$, $w_3 = 5$, $w_4 = 8$, and $v_1 = 2$, $v_2 = 3$, $v_3 = 4$, $v_4 = 5$.

Solving this using greedy algorithms (add the most valuable item that fits, etc.) doesn't yield an optimal solution. Follow the DP approach to try to identify how an optimal solution is related to optimal solutions for subproblems.

If $i_1, \ldots, i_{k-1}, i_k$ is an optimal solution, then we can at least say that $i_i, \ldots, i_{k-1}$ must be an optimal solution for a knapsack with capacity $C-w_{i_k}$. This suggests we can define an array $V[]$, where $V[j]$ is the maximum value that can be carried in a knapsack with capacity $j$. If we can find $V[C]$, then we're done. What we already know yields a recurrence:

$$V[n] = \begin{cases} 0 & n = 0\\ \max \{ V[j-1], \max_{w_i \leq j} \{v_i + V[j - w_i]\} \} & \text{otherwise} \end{cases}.$$

If you use the straight-forward approach of writing a recurrence program, you will have an extremely expensive (in running time) algorithm. Instead, compute the values bottom-up as follows (C is as above, v[i] is $v_i$, and w[i] is $w_i$):

V[0] = 0;
for (int j = 1; j <= C; j++) {
    V[j] = V[j-1];
    for (int i = 0; i < n; i++) {
        if (w[i] <= j && v[i] + V[j-w[i]] > V[j]) {
            V[j] = v[i] + V[j-w[i]];
        }
     }
}

Now you know the value of the loot you can carry away in your knapsack, but you still need to work out the actual composition. One way to do this is by creating an extra array L[j], containing the last choice of article added to get V[j].