CODEWITHSUNDEEP
pythonparametersknapsack-problem
Tweakforce_LG
Tweakforce_LG

Reputation: 117

Making sense of Knapsack brute force program

I was given a Knapsack brute force program by a friend that I want to understand. This is the code I was given:

def knapSack(W, wt, val, n):

    if n == 0 or W == 0:
        return 0


    if (wt[n - 1] > W):
        return knapSack(W, wt, val, n - 1)


    else:
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
               knapSack(W, wt, val, n - 1))




values = [10, 500, 786]
wt = [1, 2, 0.5]
weight = 2
n = len(values)
print(knapSack(weight   , wt, values, n))

I don't understand how this works:

if (wt[n - 1] > W):
return knapSack(W, wt, val, n - 1)

Nor do i understand how this works:

else:
    return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
               knapSack(W, wt, val, n - 1))

TBH i'm clueless on how these two lines work, they look like random calling of knapsack. I also don't understand what n-1 does.

I know its quite vague a request sorry :)

Upvotes: 1

Views: 1294

Answers (2)

Lawrence Chernin
Lawrence Chernin

Reputation: 151

The above is not strictly Dynamic Programming. In DP there is a table and the code does not have the potential hitting the recursion depth limit in Python.

def unboundedKnapsack(W, n, val, wt):

    dp = [0 for i in range(W + 1)]

    ans = 0

    for i in range(W + 1):
        for j in range(n):
            if (wt[j] <= i):
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j])

    return dp[W]

W = 60
val = [ 1, 20]
wt = [1, 30]


n = len(val)

print(unboundedKnapsack(W, n, val, wt))

Upvotes: 0

Saedeas
Saedeas

Reputation: 1578

The basis of the knapsack problem is as such: Given a set of items, each with a value and a weight, find the most valuable combination of items underneath a given weight limit.

These are the variables in your problem (aside: your friend's naming conventions are really bad).

There are two terminal cases in this problem:

  1. No items remaining

  2. No weight remaining

How does the program address these?

if n == 0 or W == 0:
        return 0

The second block of code is another case

Weight limit exceeded by item being tested

if (wt[n - 1] > W):
        return knapSack(W, wt, val, n - 1)

This just means attempt another iteration of the knapsack algorithm with the item currently being tested removed.

The else block here is the final piece of the puzzle

Weight limit not exceeded by item being tested

else:
    return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
           knapSack(W, wt, val, n - 1))

What is this actually saying? Return the maximum of two options:

  1. The current item's value + the value from performing the knapsack algorithm again with a lower weight limit (the W-wt[n-1] part) and the item excluded (the n-1 part).

  2. The knapsack algorithm with the current item excluded and the weight limit the same (think a case where the current item is heavy, but not worth much, this option would probably be higher).

This works because you're essentially saying take this item's value, add it in, adjust the weight, and see what the best remaining combo is, or don't include this item, and see what the best remaining combo is. This tests every possible combination of sub-options.

This whole thing is an example of a paradigm known as Dynamic Programming. I'd suggest reading up on it for some simpler examples of problems similar to this one. Once you grok the way to approach these problems, understanding them becomes much easier.

Upvotes: 2

Related Questions