title: Linear algorithm to find minimum subset sum over a threshold
body: <p>I have a collection of N positive integers, each bounded by a (relatively small) constant C. I want to find a subset of these numbers with the smallest sum greater than (or equal to) a value K.</p>
  
  <p>The numbers involved aren't terribly large (&lt;100), but I need good performance even in the worst case. I thought maybe I could adapt Pisinger's dynamic programming algorithm to the task; it runs in O(NC) time, and I happen to meet the requirements of bounded, positive numbers.</p>
  
  <p>[Edit]: The numbers are not sorted and there may be duplicates.</p>
  
  <p>However, I don't understand the algorithm well enough to do this myself. In fact, I'm not even certain if the assumptions it is based on still hold...</p>
  
  <p>-Is it possible to adapt this algorithm to my needs?</p>
  
  <p>-Or is there another linear algorithm I could use that is similarly efficient?</p>
  
  <p>-Could anyone provide pseudocode or a detailed explanation?</p>
  
  <p>Thanks.</p>
  
  <p>Link to the Subset-Sum code I was investigating:
  <a href="https://stackoverflow.com/questions/9962568/fast-solution-to-subset-sum-algorithm-by-pisinger">Fast solution to Subset sum algorithm by Pisinger</a></p>
  
  <p>(Apologies if this is poorly worded/formatted/etc. I'm still new to StackOverflow...)</p>