title: Knapsack with min weight
body: <p>This variation of the knapsack problem requires a minimum weight. The goal is to minimize the cost while achieving at least the minimum weight.</p>
  <p>For example, we have 6 items with weights <code>{1, 1, 1, 5, 13, 3}</code> and costs <code>{1, 1, 1, 5, 10, 12}</code>.
  Assume a minimum weight of 15.</p>
  <p>The optimal solution is items <code>{1, 2, 5}</code> for a total weight of 15 and cost 12.</p>
  <p>How should I go about implementing this algorithm as efficiently as possible? Greedy choices don't work, so should I modify the original dynamic programming solution to fit this problem? If so, how?</p>
  <p>If it matters, I'm planning to write this in Java.</p>