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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.