[solved] DP - Maximum Weighted Independent Sets

general
, , , , , ,
1

I am solving a problem in which you are given a tree in the form of a graph and weights at it’s each node. You need to find the Maximum Weighted Independent Sets of that tree in which tree root is unknown. However, answer will be independent of the root you take in the tree.
My code with problem description is given here can anybody help me out with my code bug.
Code is in Java

http://ideone.com/yMoBH2

Current Output:
18
Expected Output:
11

1 Like
2

I found this on geeksforgeeks This should help you.
// A naive recursive implementation of Largest Independent Set problem
#include <stdio.h>
#include <stdlib.h>

// A utility function to find max of two integers
int max(int x, int y) { return (x > y)? x: y; }

/* A binary tree node has data, pointer to left child and a pointer to
right child */
struct node
{
int data;
struct node *left, *right;
};

// The function returns size of the largest independent set in a given
// binary tree
int LISS(struct node *root)
{
if (root == NULL)
return 0;

// Caculate size excluding the current node
int size_excl = LISS(root->left) + LISS(root->right);

// Calculate size including the current node
int size_incl = 1;
if (root->left)
   size_incl += LISS(root->left->left) + LISS(root->left->right);
if (root->right)
   size_incl += LISS(root->right->left) + LISS(root->right->right);

// Return the maximum of two sizes
return max(size_incl, size_excl);

}

// A utility function to create a node
struct node* newNode( int data )
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}

// Driver program to test above functions
int main()
{
// Let us construct the tree given in the above diagram
struct node *root = newNode(20);
root->left = newNode(8);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
root->right = newNode(22);
root->right->right = newNode(25);

printf ("Size of the Largest Independent Set is %d ", LISS(root));

return 0;

}

3

I have already gone through this implementation by GeeksForGeeks. But bug of my code is still unresolved. I guess you have not gone through the question which was given as comment in the Ideone link of the question. It is different from the solution you are given. In that problem you are not given the root of the tree and still you have to find out the Max. Weighted Independent Set.

1 Like