algorithm - Minimization of the Unbounded Knapsack with Dynamic Programming -

i curious if possible modify (or use) dp algorithm of unbounded knapsack problem minimize total value of items in knapsack while making total weight at least minimum constraint c.

---

a bottom-up dp algorithm maximization version of ukp:

let w = set of weights (0-indexed)  , v = set of values (0-indexed)      dp[i][j] = max{ dp[i-1][j], dp[i][j - w[i-1]] + v[i-1] }  = 0,...,n , j = 0,...,c  given dp[0][j] = 0 , dp[i][0] = 0  n = amount of items  , c = maximum weight  dp[n][c] = maximum value of items knapsack capacity of c  

---

can make minimization ukp ? if not, can offer solution or technique solve problem this?

thanks, dan

you'll have new recurrence

dp[i][j] (       j <= 0) = 0 dp[i][j] (i = 0, j >  0) = infinity dp[i][j] (i > 0, j >  0) = min{ dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1] }, 

which gives, each i , j, minimum value of items 0..i-1 make weight @ least j. infinity should sufficiently large value such legitimate value smaller infinity.

notice dp[i][j] = 0 j <= 0 specified. indexing j - w[i-1] produce negative value second index. these negative indices j in matrix dp should give value 0 algorithm work.

additionally, definition of dp[i][j], 1 might expect non-zero values dp[i][0], since j=0 corresponds minimum weight of 0, dp[i][0] = 0 i necessary dp algorithm.