Consider a modified Knapsack Problem where:
- The number of items to be included is fixed.
- 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?