speedster's blog

Stuck on dynamic programming.
By speedster, history, 7 years ago, In English

problem : in a rooted binary tree with n nodes, each node has a positive value( v(i) ) you need to select k(k<=n) nodes from the tree. if a node is selected you must select all of its ancestors.design a dp algo for maximum possible value of k selected nodes

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First, let's observe that it's never optimal to select a non-leaf node. If the constraint are small enough (n * k2 ≤ 108) or something like that, then the following solution will work.

Now let vali be the value associated with node i and DP[v][k] be the maximum value we can achieve by selecting k nodes on the subtree rooted at v. If v is a leaf, then DP[v][k] = valv for k = 1 and 0 otherwise. If v is not a leaf, let l and r be its left and right children, then recurrence is DP[v][k] = max(DP[l][x] + DP[r][k - x]) + valv for x in range [0, k].

Do you have a link to the problem?

→ Reply