Let P be a path on n nodes where the ith node is v_i. Suppose v_i has weight w_i

Question

Let P be a path on n nodes where the ith node is v_i. Suppose v_i has weight w_i for i = 1,..., n. Let S be a subset of nodes in P. The weight of S is simply the sum of the weights of the nodes in S. We say that S is an independent set if no two nodes in S are joined by an edge. Our goal is to find an independent set in P whose total weight is as large as possible. Consider the example below which is a path on 5 vertices. The set {v_1, v_3, v_5} is an independent set whose weight is 1 + 6 + 6 = 12. The set {v_2, v_5} is another independent set and its weight of 14 is the largest among all independent sets in the graph. Design a dynamic programming algorithm that finds an the maximum total weight that an independent set in P can have. What is the runtime of your algorithm?

Explanation / Answer

  
   Input W[n] containing weights of all Vi
   --------------------------------------------
   Step1 : integer OPT[n] //declaring integer arrar for memoization
Step2 : OPT[0] = 0
Step3 : OPT[1] = Weight[1]

   Step4 : Loop for i = 2 to n :
   Step5 :   OPT[i] = max( OPT[i-1] , OPT[i-2] + Weight[i] ) //Filling the memoized array
   Step 6: End Loop
  
   Step 7: Diplay OPT[n] // OPT[n] contains the largest weighted independent set
  
   Runtime of the above algorithm is O(n) [only one loop for n elements].

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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