November 15

Wednesday we looked at how to find the highest value that can be packed into a knapsack with capacity $C$, $n$ items with weights $w_1$, ..., $w_n$, and values $v_1$, ..., $v_n$. That algorithm told us how find the highest value we can pack into the knapsack, but now which items to pack. Add an array $L[j]$ (the index of the last item packed into an optimal packing not exceeding capacity $j$), and we can track the choices of what fills up an ideal knapsack:

V[0] = 0;
for (int j = 1; j <= C; j++) {
    V[j] = V[j-1];
    L[j] = L[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]];
            L[j] = i;
        }
     }
}

Now we can work backwards from $L[C]$. We know we added item with index $L[C]$, and that item had weight $w[L[C]]$, so the previous item must have been $L[C-w[L[C]]]$, and so on.