Introduction
The 0/1 Knapsack Problem involves selecting items to maximize the total
value while keeping the total weight within a given capacity. Using the
Branch and Bound technique, we systematically explore subsets of items
to find the optimal solution, pruning branches that cannot lead to better
solutions.
Steps in Branch and Bound for 0/1 Knapsack
Problem
1. Formulation:
• Input: A set of n items, each with:
– Value v[i]
– Weight w[i]
• Knapsack capacity W .
• Decision: Include an item (1) or exclude it (0).
• Objective: Maximize total value
P P
v[i] while w[i] ≤ W .
2. Branching:
• At each node, decide whether to include or exclude an item.
3. Bounding:
• Calculate an upper bound to estimate the maximum value achiev-
able from the current node.
• Use the fractional knapsack approach for bounding:
– Include items fully until capacity allows.
– Add a fraction of the next item’s value if capacity is exceeded.
4. Pruning:
• Discard branches if:
– Weight exceeds W .
– The upper bound is less than the current best solution.
5. Search Strategy:
• Use a priority queue to explore promising nodes first (best-first
search).
1
Example
Problem Statement
Items:
• Item 1: (v = 40, w = 2)
• Item 2: (v = 100, w = 5)
• Item 3: (v = 50, w = 10)
Knapsack Capacity W = 10.
Step-by-Step Solution
1. Sort items by value/weight ratio:
• Item 2: v/w = 20
• Item 1: v/w = 20
• Item 3: v/w = 5
2. Calculate Upper Bound:
• Include Item 2 and Item 1 fully: 100 + 40 = 140.
• Capacity left: 10 − 5 − 2 = 3.
• Add 3
10
of Item 3’s value: 50 × 3
10
= 15.
• Total upper bound = 140 + 15 = 155.
3. Branch:
• Root node represents no items included, upper bound = 155.
4. Expand Root Node:
• Include Item 2:
– Weight = 5, Value = 100.
– New capacity = 10 − 5 = 5.
– Upper bound: 100 + 40 = 140 (Item 1 fully fits, no fraction
needed).
• Exclude Item 2:
– Upper bound = 155 (previous calculation).
2
5. Expand Node (Include Item 2):
• Include Item 1:
– Weight = 5 + 2 = 7, Value = 100 + 40 = 140.
– Upper bound: No more items fit, so bound = 140.
• Exclude Item 1:
– Upper bound = 100 + 15 = 115 (fractional part of Item 3).
6. Explore Best Node:
• Node with 140 (Include Item 2 and Item 1).
• Further exploration not needed as no better solution exists.
Optimal Solution
• Items included: Item 2, Item 1.
• Total Value: 140.
• Total Weight: 7.
Additional Example
Problem Statement
Items:
• Item 1: (v = 60, w = 10)
• Item 2: (v = 100, w = 20)
• Item 3: (v = 120, w = 30)
Knapsack Capacity W = 50.
Step-by-Step Solution
1. Sort items by value/weight ratio:
• Item 1: v/w = 6
• Item 2: v/w = 5
• Item 3: v/w = 4
3
2. Calculate Upper Bound:
• Include Item 1 and Item 2 fully: 60 + 100 = 160.
• Remaining capacity = 50 − 10 − 20 = 20.
• Include 20
30
of Item 3: 120 × 20
30
= 80.
• Total upper bound = 160 + 80 = 240.
3. Branch:
• Root node: No items included, upper bound = 240.
4. Expand Root Node:
• Include Item 1:
– Weight = 10, Value = 60.
– Remaining capacity = 50 − 10 = 40.
– Upper bound: 60 + 100 + 10
30
× 120 = 230.
• Exclude Item 1:
– Upper bound = 240 (all items considered fractionally).
5. Expand Node (Include Item 1):
• Include Item 2:
– Weight = 10 + 20 = 30, Value = 60 + 100 = 160.
– Remaining capacity = 50 − 30 = 20.
– Upper bound: 160 + 20
30
× 120 = 240.
• Exclude Item 2:
40
– Upper bound = 60 + 30
× 120 = 220.
6. Expand Node (Include Item 1 and Item 2):
• Include 20
30
of Item 3:
– Total value = 60 + 100 + 80 = 240.
Optimal Solution
• Items included: Item 1, Item 2, 20
30
of Item 3.
• Total value: 240.
• Total weight: 50.
