title: Maximum Sum for Subarray with fixed cutoff
body: <p>I have a list of integers, and I need to find a way to get the maximum sum of a subset of them, adding elements to the total until the sum is equal to (or greater than) a fixed cutoff. I know this seems similar to the knapsack, but I was unsure whether it was equivalent.</p>
  
  <p>Sorting the array and adding the maximum element until sum &lt;= cutoff does not work. Observe the following list:</p>
  
  <pre><code>list = [6, 5, 4, 4, 4, 3, 2, 2, 1]
  cutoff = 15
  </code></pre>
  
  <p>For this list, doing it the naive way results in a sum of 15, which is very sub-optimal. As far as I can see, the maximum you could arrive at using this list is 20, by adding 4 + 4 + 4 + 2 + 6. If this is just a different version of knapsack, I can just implement a knapsack solution, as I probably have small enough lists to get away with this, but I'd prefer to do something more efficient.</p>