Вот задача, где веса равны стоимостям.

    1 2 3 4
w = 4 2 1 3

f: s
k  0 1 2 3 4 5 6 7 8 9 10
0  1 0 0 0 0 0 0 0 0 0 0
1  1 0 0 0 1 0 0 0 0 0 0
2  1 0 1 0 1 0 1 0 0 0 0
3  1 1 1 1 1 1 1 1 0 0 0
4  1 1 1 1 1 1 1 1 1 1 1
---------------------------------------
g: 0 3 2 3 1 3 2 3 4 4 4 +oo +oo +oo...
   ^       ^ ^
           1 3
Восстановление ответа: 5 -> 4 -> 1 -> 0.
                    взяли вещь 3
                          взяли вещь 1