FO7's blog

By FO7, history, 16 months ago, In English

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

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).