We are given a tree, and a set of cost and items associated with each node. We have to compute the optimal spending of ‘k’ rupees to buy maximum number of items, is we start at the root. and travel each edge exactly once.
Get all the root to leaf paths using DFS.
On reaching a leaf, use knapsack to calculate the max no. of items in that root to leaf path.
On seeing the question, we notice that it is a tree. So there won’t be multiple cycles.
Imagine the same question asked for tree whose nodes are connected in a straight line like
The problem breaks down to a knapsack.
So we convert the given problem into the desired form
We can get all the unique root to leaf paths by a single DFS traversal.
On reaching a leaf node, we use the knapsack to calculate the maximum acheivable value in that path.
dfs(node, stack, visited): visited[node] = true stack.push(node) leaf = true for neighbours of node: if visited[neighbour] = false: dfs(neighbout, stack, visited) leaf = false if leaf == true: Knapsack(stack) stack.pop()
Maintain a knapsack at each node and add to it while travelling to children.