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?