Knapsack with minimum cost

问题:

I've got several types of coins, each have weight (wi) and cost (ci). So I've got to make a knapsack with weight==W and (!) minimum cost of coins in it. I can`t make recurrence relation to use DP.

回答1:

Just formulate the usual recurrence relation...

Designate the minimum cost achievable with total weight k as Min_cost(k).

Bootstrap the memoization with:

Min_cost(0) = cost of empty set = 0

Then solve for increasing values of k using:

Min_cost(i+1) = min [Min_cost(i)   + min [ci, for all items with wi = 1],
                     Min_cost(i-1) + min [ci, for all items with wi = 2],
                     Min_cost(i-2) + min [ci, for all items with wi = 3],
                     ...
                     Min_cost(2) + min [ci, for all items with wi = w-1],
                     Min_cost(1) + min [ci, for all items with wi = w],
                     Min_cost(0) + min [ci, for all items with wi = w+1]]