title: Minimization of the Unbounded Knapsack with Dynamic Programming
body: <p>I am curious if it is possible to modify (or use) a DP algorithm of the <strong>Unbounded Knapsack Problem</strong> to <strong>minimize</strong> the total value of items in the knapsack while making the total weight <strong>at least</strong> some minimum constraint C. </p>
  
  <hr>
  
  <p>A bottom-up DP algorithm for the maximization version of UKP:</p>
  
  <pre><code>let w = set of weights (0-indexed)
  
  and v = set of values (0-indexed)
  
      DP[i][j] = max{ DP[i-1][j], DP[i][j - w[i-1]] + v[i-1] }
  
  for i = 0,...,N and j = 0,...,C
  
  given DP[0][j] = 0 and DP[i][0] = 0
  
  where N = amount of items
  
  and C = maximum weight
  
  DP[N][C] = the maximum value of items for a knapsack capacity of C 
  </code></pre>
  
  <hr>
  
  <p>Can we make a minimization UKP ? If not, can anyone offer another solution or technique to solve a problem like this?</p>
  
  <p>Thanks, Dan</p>