0
$\begingroup$

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?

$\endgroup$

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.