CODEWITHSUNDEEP
algorithmgraphdynamic-programminggraph-algorithm
himanshu098
himanshu098

Reputation: 21

Calculate maximum profit under given path cost

Rooted Graph is given. Here, nodes is "home" that contains some valuable item. Entry node is given, i.e., root of the graph.

Cost is also given to move from one node to other, i.e., Egde weight.

Question -

You have to collect maximum valuable item, and total cost should not exceed with given cost.

Contraint - 1. There is no cycle. 2. We can use adjancency matrix also.(Total number of vertices is upto 1000).

Example

Edges given with their weight and values present in destination node.

0 1 10 1
0 2 10 15
1 3 50 10
1 4 30 30

Given Cost = 70.

Solution - You will collect node 1, 2, 4's items in a maximum way. [1+15+30 = 46]

My efforts

I think, this problem will solve by DP, by maintaining some state at every node. But I am not able to make some algorithm. Please help.

Edit 1

  1. I think this question may be solved by making special graph by using original graph by ading some state into each node.
  2. Second approach is, Dynamic programming.

Upvotes: 2

Views: 1065

Answers (1)

6502
6502

Reputation: 114461

I don't think you're going to find an easy solution for this problem.

Consider a graph made by just a root node connected to N leaves. Each leaf has a value of 1 and the edges have cost c1, c2, ... cN.

As you can see this graph problem has the knapsack problem as a special case.

Upvotes: 1

Related Questions