2. Suppose we are given a \"chain\" of n nodes as shown below. Each node i is \"

Question

2. Suppose we are given a "chain" of n nodes as shown below. Each node i is "neigh- bors" with the node to its left and the node to its right (if they exist). An inde- pendent set of these nodes is a subset of the nodes such that no two of the chosen nodes are neighbors. In the below example, the first and fourth vertices form an independent set, but the first, third, and fourth vertices do not (because the third and fourth are neighbors. Now suppose each node has a positive weight. We are interested in computing an independent set such that the sum of the weights of the chosen nodes are as large as possible. In the example, the optimal solution is to choose the second and fourth vertices for a weight of 30

Explanation / Answer

Java code with recurrence relation:

class MaximumSum
{
   /*Function to return max sum such that no two elements
   are adjacent */
   int FindMaxSum(int arr[], int start, int n, boolean canUseFirst)
   {
       if(start==n-1) {
           if(canUseFirst)
               return arr[start];
           else
               return 0;
       }
       if(canUseFirst) {          
           int sumWithout = FindMaxSum(arr, start+1, n, true);
           int sumWith = arr[start] + FindMaxSum(arr, start+1, n, false);
           return (sumWithout > sumWith)? sumWithout: sumWith;
       } else {
           return FindMaxSum(arr, start+1, n, true);
       }
   }

   // Driver program to test above functions
   public static void main(String[] args)
   {
       MaximumSum sum = new MaximumSum();
       int arr[] = new int[]{5, 5, 10, 100, 10, 5};
       System.out.println(sum.FindMaxSum(arr, 0, arr.length, true));
   }
}


Java code with Dynamic Programmming incorporated:

class MaximumSum
{
   static int maxSumsWithUseFirst[];
   static int maxSumsWithoutUseFirst[];
  
   /*Function to return max sum such that no two elements
   are adjacent */
   int FindMaxSum(int arr[], int start, int n, boolean canUseFirst)
   {
       if(start == n-1) {
           if(canUseFirst)
               return arr[start];
           else
               return 0;
       }
      
       if(canUseFirst) {          
           int sumWithout, sumWith;
          
           if(maxSumsWithUseFirst[start+1] != 0) {
               sumWithout = maxSumsWithUseFirst[start+1];
           } else {
               sumWithout = FindMaxSum(arr, start+1, n, true);
           }
          
           if(maxSumsWithoutUseFirst[start+1] != 0) {
               sumWith = arr[start] + maxSumsWithoutUseFirst[start+1];
           } else {
               sumWith = arr[start] + FindMaxSum(arr, start+1, n, false);
           }
          
           maxSumsWithUseFirst[start] = (sumWithout > sumWith)? sumWithout: sumWith;
          
           return maxSumsWithUseFirst[start];
          
       } else {
           maxSumsWithoutUseFirst[start] = FindMaxSum(arr, start+1, n, true);
           return maxSumsWithoutUseFirst[start];
       }
   }

   // Driver program to test above functions
   public static void main(String[] args)
   {
       int arr[] = new int[]{5, 5, 10, 100, 10, 5};
       MaximumSum sum = new MaximumSum();
       maxSumsWithUseFirst = new int[arr.length];
       maxSumsWithoutUseFirst = new int[arr.length];
      
       System.out.println(sum.FindMaxSum(arr, 0, arr.length, true));
   }
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.