Need Help in this DP problem !
Difference between en3 and en4, changed 57 character(s)
Given a undirected graph(Total No of Nodes is 1e5) .each node has its beauty .each edge has its own time travel cost .U have some finite time say m(<=100).U are at root node of graph.U have to travel those nodes and return to root .find the maximum beauty that u can collect.↵
Idea is by knapsack .But I am facing difficulty in calculating dp states.Please confirm if it is Np-hard problem .(As i correctly remember this was asked in coding test )↵
↵
Thanks

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English FO7 2023-08-17 15:33:39 57
en3 English FO7 2023-08-17 14:47:59 41
en2 English FO7 2023-08-17 13:23:16 8 Tiny change: ' edge has time trav' -> ' edge has its own time trav'
en1 English FO7 2023-08-17 13:22:24 382 Initial revision (published)