Solving the Knapsack Problem by Branch and Bound Algorithm
Problem Statement
• Knapsack Capacity (W): 10
• Items:
– Item 1: Weight = 4, Value = $40
– Item 2: Weight = 7, Value = $42
– Item 3: Weight = 5, Value = $25
– Item 4: Weight = 3, Value = $12
Goal: Maximize the total value of items placed in the knapsack without exceeding its capacity.
Branch and Bound Algorithm Steps
The Branch and Bound algorithm explores the solution space by building a state-space tree. Each node
in the tree represents a partial solution. We use bounds to prune branches that cannot lead to an optimal
solution.
1. Calculate Value-to-Weight Ratios (for bounding)
This helps in calculating an upper bound for the current node. We sort items by decreasing value-to-
weight ratio.
Item Weight (w) Value (v) v/w Ratio
1 4 $40 10
2 7 $42 6
3 5 $25 5
4 3 $12 4
(Note: In this specific instance, the items are already ordered by decreasing value-to-weight ratio, so
no reordering is needed for the upper bound calculation.)
2. Initialize Global Best Solution
• ‘max value = 0‘ (current best value found)
3. Node Structure for Branch and Bound
Each node in our search tree will typically have:
• ‘level‘: The current item being considered (from 0 to n).
• ‘currentw eight‘ : W eightof itemsincludedsof ar.‘currentv alue‘ : V alueof itemsincludedsof ar.
• ‘bound‘: An upper bound on the maximum value that can be obtained from this node downwards.
4. How to Calculate the Bound
The bound is calculated using the greedy approach (fractional knapsack) for the remaining items.
For a node (level i, current weight, current value):
bound = current value
remaining capacity = W − current weight
Iterate from item i to n:
• If remaining capacity ≥ weight[item j]:
– bound+ = value[item j]
– remaining capacity− = weight[item j]
1
• Else (if the item doesn’t fit completely):
– bound+ = (value[item j]/weight[item j]) ∗ remaining capacity
– remaining capacity = 0
– Break
5. Branch and Bound Steps (Building the State-Space Tree)
We’ll use a priority queue (or similar structure) to store nodes, ordered by their bounds (descending).
Initial Node (Root):
• ‘level = 0‘ (before considering any item)
• ‘currentw eight = 0“currentv alue = 0‘
• ‘bound = CalculateBound(0, 0, 0)‘
Let’s calculate the initial bound:
• Items sorted by v/w: Item 1 (4, $40), Item 2 (7, $42), Item 3 (5, $25), Item 4 (3, $12)
• ‘remainingc apacity = 10‘AddItem1 : ‘bound = 40‘, ‘remainingc apacity = 10 − 4 = 6‘
• Add Item 2 (partially): Item 2 weight is 7, but ‘remainingc apacity‘is6.
• ‘bound += (42/7) * 6 = 6 * 6 = 36‘
• ‘bound = 40 + 36 = 76‘
• ‘remainingc apacity = 0‘
So, initial ‘bound = 76‘.
Search Process:
We’ll explore nodes. For each item, we have two branches:
• a) Include the item.
• b) Exclude the item.
We prune branches if:
1. The ‘currentw eight‘exceeds‘W ‘.T he‘bound‘of anodeislessthanorequalto‘maxv alue‘.
Node 1: (Root - level 0)
2.• ‘level = 0‘, ‘cw = 0‘, ‘cv = 0‘, ‘bound = 76‘ (Initial upper bound)
• ‘maxv alue = 0‘
Branch 1.1: Include Item 1 (weight 4, value 40)
• ‘level = 1‘
• ‘cw = 4‘
• ‘cv = 40‘
• ‘bound = CalculateBound(level 1, cw 4, cv 40)‘:
– Remaining capacity: 10 − 4 = 6
– Items remaining: Item 2 (7, $42), Item 3 (5, $25), Item 4 (3, $12)
– Add Item 2 (fractionally): 40 + (42/7) ∗ 6 = 40 + 36 = 76
• Node 1.1: ‘(level 1, cw 4, cv 40, bound 76)‘
Branch 1.2: Exclude Item 1
• ‘level = 1‘
2
• ‘cw = 0‘
• ‘cv = 0‘
• ‘bound = CalculateBound(level 1, cw 0, cv 0)‘:
– Remaining capacity: 10 − 0 = 10
– Items remaining: Item 2 (7, $42), Item 3 (5, $25), Item 4 (3, $12)
– Add Item 2: 0 + 42 = 42, ‘remaining = 3‘
– Add Item 3 (partially): 42 + (25/5) ∗ 3 = 42 + 15 = 57
• Node 1.2: ‘(level 1, cw 0, cv 0, bound 57)‘
Current ‘maxv alue = 0‘
N odestoexplore(sortedbybound, descending) : ‘(N ode1.1 : bound76), (N ode1.2 : bound57)‘
Explore Node 1.1: ‘(level 1, cw 4, cv 40, bound 76)‘
Branch 1.1.1: Include Item 2 (weight 7, value 42)
• ‘level = 2‘
• ‘cw = 4 + 7 = 11‘
• ‘cv = 40 + 42 = 82‘
• PRUNE! ‘cw (11)‘ ¿ ‘W (10)‘. This path is invalid.
Branch 1.1.2: Exclude Item 2
• ‘level = 2‘
• ‘cw = 4‘
• ‘cv = 40‘
• ‘bound = CalculateBound(level 2, cw 4, cv 40)‘:
– Remaining capacity: 10 − 4 = 6
– Items remaining: Item 3 (5, $25), Item 4 (3, $12)
– Add Item 3: 40 + 25 = 65, ‘remaining = 1‘
– Add Item 4 (fractionally): 65 + (12/3) ∗ 1 = 65 + 4 = 69
• Node 1.1.2: ‘(level 2, cw 4, cv 40, bound 69)‘
Current ‘maxv alue = 0‘
N odestoexplore : ‘(N ode1.1.2 : bound69), (N ode1.2 : bound57)‘
Explore Node 1.1.2: ‘(level 2, cw 4, cv 40, bound 69)‘
Branch 1.1.2.1: Include Item 3 (weight 5, value 25)
• ‘level = 3‘
• ‘cw = 4 + 5 = 9‘
• ‘cv = 40 + 25 = 65‘
• ‘bound = CalculateBound(level 3, cw 9, cv 65)‘:
– Remaining capacity: 10 − 9 = 1
– Items remaining: Item 4 (3, $12)
– Add Item 4 (fractionally): 65 + (12/3) ∗ 1 = 65 + 4 = 69
• Node 1.1.2.1: ‘(level 3, cw 9, cv 65, bound 69)‘
3
Branch 1.1.2.2: Exclude Item 3
• ‘level = 3‘
• ‘cw = 4‘
• ‘cv = 40‘
• ‘bound = CalculateBound(level 3, cw 4, cv 40)‘:
– Remaining capacity: 10 − 4 = 6
– Items remaining: Item 4 (3, $12)
– Add Item 4: 40 + 12 = 52, ‘remaining = 3‘
• Node 1.1.2.2: ‘(level 3, cw 4, cv 40, bound 52)‘
Current ‘maxv alue = 0‘
N odestoexplore : ‘(N ode1.1.2.1 : bound69), (N ode1.2 : bound57), (N ode1.1.2.2 : bound52)‘
Explore Node 1.1.2.1: ‘(level 3, cw 9, cv 65, bound 69)‘
Branch 1.1.2.1.1: Include Item 4 (weight 3, value 12)
• ‘level = 4‘
• ‘cw = 9 + 3 = 12‘
• ‘cv = 65 + 12 = 77‘
• PRUNE! ‘cw (12)‘ ¿ ‘W (10)‘. This path is invalid.
Branch 1.1.2.1.2: Exclude Item 4
• ‘level = 4‘
• ‘cw = 9‘
• ‘cv = 65‘
• This is a leaf node (all items considered).
• ‘currentv alue(65)‘ > ‘maxv alue(0)‘.U pdate‘maxv alue = 65‘.Currentbestsolution : Items1and3.
• Node 1.1.2.1.2: ‘(level 4, cw 9, cv 65, bound 65)‘ (No more items to add, so bound equals
current value)
Current ‘maxv alue = 65‘
N odestoexplore : ‘(N ode1.2 : bound57), (N ode1.1.2.2 : bound52)‘
Pruning Check:
• Node 1.2: ‘bound (57)‘ is less than or equal to ‘maxv alue(65)‘.PRUNE!(T hisbranchcannotleadtoabettersolutiont
‘bound(52)‘isless than or equal to‘maxv alue(65)‘.PRUNE!(T hisbranchcannotleadtoabettersolutionthan65).
All active branches have been explored or pruned.
6. Final Result:
The maximum value found is $65. The items corresponding to this value are Item 1 (Weight
4, Value $40) and Item 3 (Weight 5, Value $25). Total Weight = 4 + 5 = 9 (within capacity
10) Total Value = 40 + 25 = 65
This is the optimal solution for the given Knapsack problem using the Branch and
Bound algorithm.
