CODEWITHSUNDEEP
algorithmdynamic-programming
Sagar
Sagar

Reputation: 1

Choosing k vertices from binary tree vertices set such that sum of cost edges in this new k vertices subset is minimum

Given a binary tree T with a weight function on its edge set w : E -> Z (Note the weight can be negative too) and a positive integer k. For a subset T' of V (T), cost(T') is defined as the sum of the weights of edges (u, v) such that u, v ∈ T' .Give an algorithm to find a subset T' of exactly k vertices that minimizes cost(T').

How to solve this problem using dynamic programming?

Upvotes: 0

Views: 206

Answers (1)

btilly
btilly

Reputation: 46445

It is usually easier to solve dynamic programming problems top down. They are often more efficient if solved bottom up. But I'll just get you going on the easier version.

Fill out this recursive function:

def min_cost(root, count_included, include_root):
    # root is the root of the subtree
    # count_included is how many nodes in the subtree to include in T'
    # include_root is whether root will be in T'.
    #
    # It will return the minimum cost, or math.inf if no solution exists
    ...

And with that, your answer will be:

min_cost(root_of_tree, k, True) + min_cost(root_of_tree, k, False)

This is slow, so memoize for the top down.

I will leave the bottom up as a more difficult exercise.

Upvotes: 1

Related Questions