Posts tagged python

0-1 Knapsack Problem in Python


The 0-1 Knapsack problem is a variation on the knapsack problem with one condition: there is only one copy of each item. You may choose to pick it or not. Given this condition, it’s possible to iterate through the items and memoize the decisions sequentially. At each iteration of and : Check if the current item is larger than the capacity. If it is, ignore the item. In this context, ignoring the item means that for this particular combination of and , the maximum value is the same as the previous value of . If the current item can fit in the knapsack, then the maximum value for this combination of and is the larger of the values resulting from both outcomes. represents the value if you choose to ignore the item, and represents the value if you choose to put the item in your knapsack.

Iterative Tree Traversals in Python


Tree traversals are most naturally expressed in recursion, but iterative versions are cool too, plus they take only O(1) space. Inorder traversal: Visit the left subtree first, then the node, and the right subtree. Preorder traversal: Visit the node first, then the left subtree, then the right subtree. Postorder traversal: Visit the left subtree, then the right subtree, then the node. The concept behind the iterative versions are as follows. There are three states a traversal can be in: You’ve just visited the left or right child of a parent node. You’ve just gone back to a parent node from its left child. You’ve just gone back to a parent node from its right child. Keeping three pointers: to designate the previous node, to designate the current node, and to designate the next node, we can codify the above conditions like so: With that in mind, I present the three different traversals, whose function signatures take a as the first argument and a function to operate on the tree nodes as the second argument.