Get the maximum sum of n items below a threshold


Consider a modified Knapsack Problem where:

  1. The number of items to be included is fixed.
  2. The value of each item is equal to its weight.

Therefore, given a set of numbers, a threshold and the number of items to use (n), I want to get the subset of n numbers that produces the highest sum below the given threshold.

Having already asked this question a year ago and not being able to fully understand the given answers, this time I’m asking for something a little different. The dynamic programming solution to the 0-1 Knapsack Problem only became clear to me when I got to see the recursive approach first:

def knapsack(w, ws, vs, n):     # if num of items or weight left is 0 value is 0     if n == 0 or w == 0:         return 0     # if item doesn't fit return best val without item     if ws[n - 1] > w:         return knapsack(w, ws, vs, n - 1)     # otherwise, return max of best vals with and without item     include = knapsack(w - ws[n - 1], vs, w, n - 1) + v[n - 1]     not_include = knapsack(w, vs, w, n - 1)     return max(include, not_include) 

So, if I were to solve my problem using a recursive approach (for educational purposes), what would that look like? And optionally, how would it be translated to a dynamic programming solution?