01 Knapsack Algorithm – Recursion – Backtrack – Algo

Like the robots of Asimov, all recursive algorithms must obey three important laws:

  1. A recursive algorithm must have a base case.
  2. A recursive algorithm must change its state and move toward the base case.
  3. A recursive algorithm must call itself, recursively.

Remeber : http://interactivepython.org/runestone/static/pythonds/Recursion/TheThreeLawsofRecursion.html


max_weight = 15
max_items = 5
items = [ 1, 6, 2, 13, 2, 21, 5, 6, 7, 8, 9]
# #
def knapsack(current_weight=0, index=0, items_count=0):
    if items_count >= max_items or current_weight > max_weight  :
        # reached items limit
        return current_weight
    if index >= len(items):
        # reached end
        return current_weight
    # either take the item
    take = knapsack(current_weight + items[index], index + 1, items_count + 1)
    # or leave the item
    dont_take = knapsack(current_weight, index + 1, items_count)
    temp = [x for x in [current_weight, take, dont_take] if x <= max_weight]
    return max(temp)
##
print knapsack()

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s