The Breadth-First Search with Branch-and-Bound Pruning Algorithm for the D- Algo

Question

The Breadth-First Search with Branch-and-Bound Pruning Algorithm for the D- Algorithm 6.1 0-1 Knapsack problem Problem: Let n items be given, where each item has a weight and a profit The weights and profits are positive integers. Furthermore, let a positive integer W be given. Determine a set of items with maximum total profit under the constraint that the sum of their weights cannot exceed W. Inputs: positive integers n and W, arrays of positive integers w and p, each indexed from 1 to n, and each of which is sorted in nonincreasing order according to the values of p i /w li Outputs an integer marprofit that is the sum of the profits in an optimal set void knapsack 2 (int n const int p[] const int w in t int& m ar profit queue of node node u v initialize (Q); Initialize Q to be empty v. level 0; v. profit 0 v. weight 0; Initialize v to be the root m ar profit (Q, v en queue while empty (Q) de queue (Q, v); u level v. level 1; Set u to a child of v weight w w. level Set u to the child u. weight u. profit v. profit p w. level that includes the next item. if u weight W && w. profit m ar profit) m a zprofit u. profit if (bound (u) maarprofit) en queue (2, u u weight v weight Set u to the child that does not include the u. profit v. profit if (bound (w) m azprofit) next item. en queue (Q, w);

Explanation / Answer

In given example n = 5 and w = 13

Level: 0 profit: 0    weight: 0 bound: 80
Level: 1 profit: 20 weight: 2 bound: 80
Level: 2 profit: 50    weight: 7 bound: 80
Level: 2 profit: 20 weight: 2 bound: 70
Level: 3 profit: 55    weight: 9 bound: 70
Level: 4 profit: 67 weight: 12 bound: 70
Level: 1 profit: 0    weight: 0 bound: 69
Level: 3 profit: 50 weight: 7 bound: 65

The number of promising node: 6
The number of non promising node : 7
The answer is 70

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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