Knapsack Problem - Branch and Bound Technique

Overview

• Discussion on solving the knapsack problem using the branch and bound technique.
• Previous session implemented knapsack problem step-by-step but did not include construction of the state space tree.

Problem Statement

• Solve the knapsack problem with the following data:
  • Capacity of the knapsack: 10
  • Four items with corresponding weight and value.

Value by Weight Ratio

• Need to find the value by weight ratio and order items in decreasing order.
• Given that the items are already ordered, no need for further steps.

Upper Bound Calculation

• Upper bound (uv) calculated using the formula:
  • uv = v + (m - w) * (vi+1 / wi+1)
    where:
    • v = total value of all items in the knapsack
    • m = maximum capacity of knapsack
    • w = total weight of items in the knapsack
    • vi+1 / wi+1 = value by weight ratio of the next item.*

State Space Tree Construction

• The state space tree for the knapsack problem is a binary tree:
  • Left subtree: includes an item
  • Right subtree: excludes an item
• Initial state is at 0th level:
  • Weight (W) = 0, Value (V) = 0, Calculate upper bound.

Constructing the Tree

1. Item 0 (never considered): Upper bound value calculated as 100.

2. Item 1:

   • Including Item 1: Weight = 4, Value = 40, Upper bound = 76.
   • Excluding Item 1: Weight = 0, Value = 0, Upper bound = 60.
   • Choose the maximum upper bound: 76.

3. Item 2:

   • Including Item 2: Weight exceeds max capacity (not feasible).
   • Excluding Item 2: Weight = 4, Value = 40, Upper bound = 70.
   • Maximum: 70 (continue with this node).

4. Item 3:

   • Including Item 3: Weight = 9, Value = 65, Upper bound = 69.
   • Excluding Item 3: Weight = 4, Value = 40, Upper bound = 64.
   • Maximum: 69 (include item 3).

5. Item 4:

   • Including Item 4: Weight exceeds max capacity (not feasible).
   • Excluding Item 4: Remain at Weight = 9, Value = 65; Upper bound = 69.
   • Remains optimal solution.

Final Solution

• Solution Vector: Items included in knapsack: 1, 3.
• Final Upper Bound Value: 69.

Important Notes

• State space tree for knapsack is a binary tree; unlike problems such as traveling salesman or assignment.
• This video is a continuation of the previous session, which focused on calculating upper bounds without constructing the tree.

Resources

• Previous video link will be provided in the description for reference.