PROBLEM LINK:
DIFFICULTY
Easy-Medium
PREREQUISITES:
DFS, Knapsack
PROBLEM:
There are a total of ‘n’ shops with exactly ‘n-1’ corridors between different shops and each shop has atleast one path through which it can be reached from the main enterance. These corridors have a one-person-once-pass policy; i.e. a person can pass through a corridor only once (may it be in any direction).
Every shop i offers their customers a fix number of items denoted by Ai in exchange of an amount Pi. Ofcourse its on customers will to decide whether to make the deal on a shop he passes through or not. Saurabh has a fix budget of Rs ‘k’ for his shopping campaign.
We have to find the maximum number of items that can be purchased within the given budget, so that he could match up to the expectations that Saurabh has from him.
Quick Explanation:
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.
Explanation:
It is clear from the question that it is a tree. So there won’t be any cycle in the graph. We have to reach from root to leave and do a knapsack to solve to the problem. So basically one can say that problem can be divided into knapsack subproblems.
For Knapsack you can see this link.
So in this problem we are going to apply dfs and reach till leaf node and maintain a 2d matrix(as maintained in a basic knapsack solution) and calculate the items purchased in this path and again while backtracking backtracking in dfs we modify the 2d matrix and calculate items in this path and thus storing maximum of all and that will be our answer.