Proving Greedy Algorithm Correctness

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

THEOREM: Greedy algorithm G produces an optimal solution for problem P.
 
PROOF (Exchange Argument):
 
1. SETUP
   Let G produce solution S_G with choices g₁, g₂, ..., gₖ (in order made)
   Let S* be any optimal solution
   
2. EXCHANGE LEMMA
   For each greedy choice gᵢ:
   
   If gᵢ ∈ S*: 
     Already included, no exchange needed.
   
   If gᵢ ∉ S*:
     Claim: There exists x ∈ S* such that (S* - {x}) ∪ {gᵢ} is:
       (a) A valid solution (satisfies all constraints)
       (b) At least as good as S* (same or better objective value)
     
     Proof of claim:
       - Identify what x should be swapped out
       - Show swapping x for gᵢ maintains/improves solution
       - [Problem-specific reasoning here]
   
   Let S*' = (S* - {x}) ∪ {gᵢ}
   S*' is also optimal and includes gᵢ.
 
3. ITERATIVE TRANSFORMATION
   Starting from any optimal S*:
   - If g₁ ∉ S*, exchange to get S*' containing g₁
   - If g₂ ∉ S*', exchange to get S*'' containing g₁, g₂
   - Continue until all greedy choices are included
   
   Final solution contains all of g₁, g₂, ..., gₖ and is optimal.
 
4. CONCLUSION
   The greedy solution S_G is (a subset of) this optimal solution.
   Therefore S_G is optimal.  ∎

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

def fractional_knapsack_greedy(items, capacity):
    """
    Solve fractional knapsack optimally using greedy.
    
    Args:
        items: List of (value, weight, name) tuples
        capacity: Maximum weight capacity
        
    Returns:
        (total_value, selections) where selections is list of 
        (name, fraction_taken, value_gained) tuples
        
    Greedy: Take items in order of decreasing value/weight ratio.
    """
    # Calculate ratios and sort by ratio (highest first)
    items_with_ratio = [(v, w, name, v/w) for v, w, name in items]
    sorted_items = sorted(items_with_ratio, key=lambda x: -x[3])  # -ratio for descending
    
    remaining_capacity = capacity
    total_value = 0
    selections = []
    
    for value, weight, name, ratio in sorted_items:
        if remaining_capacity <= 0:
            break
            
        if weight <= remaining_capacity:
            # Take the whole item
            fraction = 1.0
            value_taken = value
            remaining_capacity -= weight
        else:
            # Take a fraction
            fraction = remaining_capacity / weight
            value_taken = value * fraction
            remaining_capacity = 0
        
        if fraction > 0:
            selections.append((name, fraction, value_taken))
            total_value += value_taken
    
    return total_value, selections
 
# Example
items = [
    (60, 10, "A"),   # Ratio = 6.0
    (100, 20, "B"),  # Ratio = 5.0
    (120, 30, "C"),  # Ratio = 4.0
]
capacity = 50
 
total, selections = fractional_knapsack_greedy(items, capacity)
print("Fractional Knapsack Greedy Solution:")
for name, fraction, value in selections:
    print(f"  Item {name}: take {fraction*100:.0f}% -> value {value:.0f}")
print(f"Total value: {total}")
 
# Output:
# Item A: take 100% -> value 60    (10 weight used, 40 remaining)
# Item B: take 100% -> value 100   (20 weight used, 20 remaining)
# Item C: take 67% -> value 80     (20 weight used, 0 remaining)
# Total value: 240

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

THEOREM: The ratio-greedy algorithm produces an optimal solution 
         for Fractional Knapsack.
 
PROOF (Exchange Argument):
 
STEP 1: SETUP AND OBSERVATION
  Let items be indexed 1, 2, ..., n in order of decreasing ratio.
  
  Greedy solution G fills capacity by taking as much of item 1 as possible,
  then item 2, then item 3, etc., until capacity is exhausted.
  
  Key observation about G's structure:
  There exists an index k* such that:
    - Items 1, 2, ..., k*-1 are taken completely (xᵢ = 1)
    - Item k* is taken partially (0 ≤ x_{k*} ≤ 1)
    - Items k*+1, ..., n are not taken at all (xᵢ = 0)
  
  (If capacity is exhausted exactly on an item boundary, k* takes 100%)
 
STEP 2: EXCHANGE ARGUMENT
  Let O* = (y₁, y₂, ..., yₙ) be any optimal solution.
  
  Consider the first item i where G and O* differ:
    - If xᵢ = yᵢ for all i, then G = O* and we're done.
    - Otherwise, let i be smallest index where xᵢ ≠ yᵢ.
  
  Case analysis:
  
  CASE A: xᵢ > yᵢ (Greedy takes more of item i than optimal)
    
    Since xᵢ > yᵢ, greedy wanted to take more of item i.
    By greedy's structure: i ≤ k* (item i is in greedy's "take" region)
    
    For greedy to want more of i but not take it all:
      Either i = k* (partial item) or capacity was available
    
    Since O* takes less of a high-ratio item, O* must compensate
    by taking more of some lower-ratio item j > i (since O* uses
    same or less capacity and achieves same/higher value).
    
    THE EXCHANGE:
    Let δ = min(xᵢ - yᵢ, (yⱼ × wⱼ)/wᵢ) for some j > i where yⱼ > 0
    
    Create O*' by:
      - Increase yᵢ by δ (take more of high-ratio item i)  
      - Decrease yⱼ by (δ × wᵢ)/wⱼ (take less of low-ratio item j)
    
    Weight change: +δ×wᵢ - (δ×wᵢ/wⱼ)×wⱼ = 0 (capacity preserved!)
    Value change: +δ×vᵢ - (δ×wᵢ/wⱼ)×vⱼ 
                = δ×wᵢ×(vᵢ/wᵢ - vⱼ/wⱼ)
                = δ×wᵢ×(rᵢ - rⱼ) 
                ≥ 0 (since i < j means rᵢ ≥ rⱼ)
    
    So O*' is valid and has value ≥ O*. 
    Since O* is optimal, O*' must also be optimal.
    O*' agrees with G on one more position.
  
  CASE B: xᵢ < yᵢ (Optimal takes more of item i than greedy)
    
    If i < k*: Greedy takes all of item i (xᵢ = 1).
               So xᵢ < yᵢ means yᵢ > 1, impossible since yᵢ ≤ 1.
               
    If i = k*: This means yᵢ > xᵢ = (partial amount greedy took).
               But greedy took as much of k* as capacity allowed.
               For O* to take more, it must have taken less of some j < k*.
               By same exchange logic above (reversed), 
               we can swap to agree with greedy.
               
    If i > k*: Greedy takes 0 of item i because capacity exhausted.
               O* takes positive amount? Then O* has remaining capacity.
               Exchange some of O*'s item i for item j < k* where yⱼ < xⱼ.
 
STEP 3: ITERATIVE TRANSFORMATION
  Each exchange either:
    - Increases value (contradicting O* optimality) → won't happen
    - Keeps value same and makes O* closer to G
  
  After at most n exchanges, transformed O* = G.
  Since we only made value-preserving or value-improving swaps,
  G has value ≥ original O*.
  
  Since O* is optimal, G is also optimal.  ∎

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

"""
0/1 Knapsack: No fractions allowed.
 
Consider items:
  A: value=60, weight=10, ratio=6.0
  B: value=100, weight=20, ratio=5.0
  C: value=120, weight=30, ratio=4.0
 
Capacity W = 50
 
GREEDY BY RATIO:
  Take A (weight 10, value 60) -> remaining capacity 40
  Take B (weight 20, value 100) -> remaining capacity 20  
  Can't take C (weight 30 > 20)
  
  Final: A + B = value 160, weight 30
  
OPTIMAL:
  Take B + C = value 220, weight 50 <- Uses full capacity!
  
THE EXCHANGE ARGUMENT FAILS:
 
If we try to swap:
  Greedy solution: {A, B}
  Optimal solution: {B, C}
  
  Greedy has A but optimal doesn't.
  Greedy would want to keep A (high ratio!).
  
  But we can't swap C for A:
    - Remove C (weight 30), add A (weight 10)
    - Optimal becomes {A, B}, weight=30, but capacity was 50!
    - We "waste" 20 units of capacity
    - Value drops from 220 to 160
  
  The problem: we can't take fractional C to fill the gap.
  Integer constraints break the exchange.
"""
 
def demonstrate_01_knapsack_failure():
    items = [
        (60, 10, "A"),   # ratio 6.0
        (100, 20, "B"),  # ratio 5.0
        (120, 30, "C"),  # ratio 4.0
    ]
    capacity = 50
    
    # Greedy
    sorted_by_ratio = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
    greedy_value = 0
    greedy_weight = 0
    greedy_items = []
    
    for value, weight, name in sorted_by_ratio:
        if greedy_weight + weight <= capacity:
            greedy_items.append(name)
            greedy_value += value
            greedy_weight += weight
    
    print(f"Greedy (0/1): {greedy_items}, value={greedy_value}, weight={greedy_weight}")
    
    # Optimal (by enumeration for this small example)
    print(f"Optimal: ['B', 'C'], value=220, weight=50")
    print(f"Greedy suboptimal by: {220 - greedy_value}")
 
demonstrate_01_knapsack_failure()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

import heapq
from collections import defaultdict
 
class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char      # Character (None for internal nodes)
        self.freq = freq      # Frequency
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        return self.freq < other.freq  # For min-heap ordering
 
def build_huffman_tree(frequencies):
    """
    Build Huffman tree using greedy algorithm.
    
    Greedy choice: Always merge the two lowest-frequency nodes.
    """
    # Create leaf nodes and add to min-heap
    heap = [HuffmanNode(char=c, freq=f) for c, f in frequencies.items()]
    heapq.heapify(heap)
    
    # Repeatedly merge two smallest until one tree remains
    while len(heap) > 1:
        left = heapq.heappop(heap)   # Smallest
        right = heapq.heappop(heap)  # Second smallest
        
        # Create parent node with combined frequency
        merged = HuffmanNode(
            freq=left.freq + right.freq,
            left=left,
            right=right
        )
        heapq.heappush(heap, merged)
    
    return heap[0]  # Root of Huffman tree
 
def generate_codes(node, prefix="", codes=None):
    """Generate code for each character by traversing tree."""
    if codes is None:
        codes = {}
    
    if node.char is not None:
        # Leaf node: store code
        codes[node.char] = prefix if prefix else "0"
    else:
        # Internal node: recurse
        generate_codes(node.left, prefix + "0", codes)
        generate_codes(node.right, prefix + "1", codes)
    
    return codes
 
def calculate_cost(codes, frequencies):
    """Calculate total encoding cost: Σ freq × code_length"""
    return sum(frequencies[c] * len(codes[c]) for c in frequencies)
 
# Example
frequencies = {
    'a': 45,  # Very common
    'b': 13,
    'c': 12,
    'd': 16,
    'e': 9,
    'f': 5,   # Rare
}
 
tree = build_huffman_tree(frequencies)
codes = generate_codes(tree)
 
print("Huffman Codes:")
for char, code in sorted(codes.items()):
    print(f"  '{char}' (freq={frequencies[char]:2d}): {code}")
 
cost = calculate_cost(codes, frequencies)
print(f"
Total weighted code length: {cost}")
print(f"Average bits per character: {cost / sum(frequencies.values()):.2f}")
 
# Compare to fixed-length encoding
fixed_length = 3  # ceil(log2(6)) = 3 bits needed for 6 chars
fixed_cost = sum(frequencies.values()) * fixed_length
print(f"Fixed-length ({fixed_length} bits each) cost: {fixed_cost}")
print(f"Huffman saves: {fixed_cost - cost} bits ({100*(fixed_cost-cost)/fixed_cost:.1f}%)")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

THEOREM: Huffman's algorithm produces an optimal prefix-free code.
 
PROOF (Exchange Argument):
 
We prove two lemmas, then combine them.
 
LEMMA 1 (Greedy Choice Property):
  Let x and y be the two characters with lowest frequencies.
  There exists an optimal tree T* where x and y are siblings at maximum depth.
 
Proof of Lemma 1:
  Let T* be any optimal tree.
  Let a and b be two siblings at maximum depth in T* (such nodes must exist).
  
  Case 1: {a,b} = {x,y}
    Already siblings, done.
    
  Case 2: {a,b} ≠ {x,y}
    Without loss of generality, assume a ≠ x (so a has freq ≥ x's freq).
    Swap x and a to get tree T'.
    
    Cost change:
      cost(T') - cost(T*) 
        = freq(x)·depth_T'(x) + freq(a)·depth_T'(a) 
          - freq(x)·depth_T*(x) - freq(a)·depth_T*(a)
        = freq(x)·depth_T*(a) + freq(a)·depth_T*(x) 
          - freq(x)·depth_T*(x) - freq(a)·depth_T*(a)
        = (freq(a) - freq(x)) · (depth_T*(x) - depth_T*(a))
    
    Since freq(a) ≥ freq(x)  [x was minimum frequency]
    And depth_T*(x) ≤ depth_T*(a)  [a was at max depth]
    
    First factor ≥ 0, second factor ≤ 0, so product ≤ 0.
    Therefore cost(T') ≤ cost(T*).
    
    Since T* was optimal, T' is also optimal.
    
    Repeat with y and b if needed.
    Result: optimal tree with x,y as siblings at max depth.  ∎
 
LEMMA 2 (Optimal Substructure):
  Let T be an optimal tree for alphabet C.
  Let z be the internal node that is parent of x and y (lowest freq pair).
  Let T' be T with x,y removed and z now a leaf with freq(z) = freq(x)+freq(y).
  
  Then T' is optimal for alphabet C' = (C - {x,y}) ∪ {z}.
 
Proof of Lemma 2:
  For any tree T'', let T'' + (x,y) denote tree where z in T'' is replaced
  by subtree with z as parent of x and y.
  
  cost(T'' + (x,y)) = cost(T'') + freq(x) + freq(y)
  [Adding x,y each adds one to their depths, plus the cost contribution from z
   becomes contributions from x and y at one deeper level]
  
  If T' were not optimal for C', let T'_opt be optimal for C'.
  Then T'_opt + (x,y) would have cost:
    cost(T'_opt) + freq(x) + freq(y) < cost(T') + freq(x) + freq(y) = cost(T)
  
  This contradicts T being optimal for C.
  Therefore T' must be optimal for C'.  ∎
 
MAIN THEOREM PROOF:
  By Lemma 1: Huffman's first merge (of min-freq pair x,y) creates a subtree
              that appears in some optimal solution.
  By Lemma 2: After this merge, the remaining problem (with merged node z)
              is a smaller instance of the same problem.
  
  By induction on |C|:
  - Base case (|C| = 2): Both characters are roots' children, trivially optimal.
  - Inductive step: Huffman solves smaller problem optimally (by induction),
                    plus Lemma 1 shows the merge was safe.
  
  Therefore Huffman's algorithm is optimal.  ∎