Блог пользователя speedster

Stuck on dynamic programming.
Автор speedster, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить