Modify the algorithm below to keep a count of the total number of nodes your alg

Question

Modify the algorithm below to keep a count of the total number of nodes your algorithm examines. You must also modify the algorithm to include the set of items in the solution. Your results must include the maximum profit, the weight of items in the bag, the percent of weight taken over total weight the bag holds, the percentage of weight taken over the weight of all possible items, the number of nodes examined and the percentage of visited nodes over all possible nodes in the state space.

Item 1: Profit $40, weight 2

Item 2: Profit $30, weight 5

Item 3: Profit $50, weight 10

Item 4: profit $10, weight 5

void knapsacks (int n, const int pl) const int l, int int & maz profit) priority queue of node PQ node u initialize (PO); Initialize P to be v. level 0; v. profit 0; v. weight 0; empty Initialize v to be the mar profit 0; bound (v) bound root insert (PQ, v); 262 Chapter 6 BRANCH-AND-BOUND while empty (PQ) Remove node with best bound remove (PQ, v if (v. bound marprofit) Check if node is still u. level v. level 1 promising w. weight v. weight w u. level Set u to t he child u-profit v. profit plu. level] that includes the next it if (u. weight W && u. profit maz profit) maar profit w. profit bound (u) u. bound if (u. bound mar profit) insert PQ, u Set u to the child u. weight v. weight that does not include v. profit is. profit bound (u) the next item. vs. bound if (vs. bound mar profit insert (P u

Explanation / Answer

examined_count=0;
while (!empty(PQ))
   remove(PQ, v)
   examined_count=examined_count+1;
   if (v.bound>maxprofit){
       u.level=v.level+1;
       u.weight=v.weight+w[u.level];
       u.profit=v.profit+p[u.level];
       u.list=v.list.append(u.level)
      
       if(u.weight<=W && u.profit > maxprofit)
       {
           maxprofit=u.profit;
           maxlist=u.list;
           maxweight=u.weight;
       }
       u.bound=bound(u)
       if(u.bound>maxprofit)
           insert(PQ,u);
       u.weight=v.weight;
       u.profit=v.profit;
       u.bound=bound(u);
       u.list=v.list
       if(u.bound>maxprofit)
           insert(PQ,u);
   }
}
weight_of_items=0;
for i in 1 to n
   weight_of_items=weight_of_items+w[i]
percent_over_bag_weight=(maxweight/W)*100;
percent_over_items_weight=(maxweight/weight_of_items)*100
percent_of_visited_nodes=(examined_count/power(2,n))*100
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

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