A depth-first dynamic programming algorithm for the Tree Knapsack Problem

The Tree Knapsack Problem (TKP) can be regarded as a 0–1 knapsack problem on a rooted tree T such that if a node is selected into a knapsack, then all nodes on the path from the selected node to the root node must also be selected into the knapsack. In this paper, we develop a pseudopolynomial-time algorithm for TKP, the depth-first dynamic programming algorithm. We prove that a TKP can be solved by our algorithm in θ(nH) time, where n is the number of nodes in T and H is the given capacity. We also report the computational results of the depth-first dynamic programming algorithm.