Like the robots of Asimov, all recursive algorithms must obey three important laws:
- A recursive algorithm must have a base case.
- A recursive algorithm must change its state and move toward the base case.
- A recursive algorithm must call itself, recursively.
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()