Non adjacent graph nodes maximum sum

Правка en1, от Ballista, 2020-02-06 08:06:08

Given a Graph $$$D$$$ of $$$N$$$ nodes, where each node $$$i$$$ has $$$C_i$$$ coins attached with it. You have to choose a subset of nodes such that no two adjacent nodes(i.e. nodes connected directly by an edge) are chosen and sum of coins attached with nodes in chosen subset is maximum.

For a tree this is a famous DP on Tree problem ( solution for Tree version here: https://mirror.codeforces.com/blog/entry/20935 -> Problem 1 ). Can we extend the DP on trees logic to solve it for a general graph. If not how can should I approach it?

Теги #graph, #dynamic programing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Ballista 2020-02-06 08:06:08 555 Initial revision (published)