Greedy Algorithms and Practical Problem-Solving Examples
Greedy algorithms solve complex problems by breaking them into sequential steps, choosing the most optimal option at each step without revising previous choices. The core assumption is that selecting local optima repeatedly will yield a global optimum.
Key Properties for Greedy Application
- Optimal Substructure: The optimal solution to the entire problem must contain optimal solutions to its subproblems.
- Greedy Choice Property: Making a locally optimal choice at each step directly leads to the global best solution.
To verify if a problem fits, rely on problem-solving experience and test for counterexamples where greedy fails.
Classic Greedy Problem Examples
1. Minimum Coin Change (Base Case & Counterexample)
For unlimited coins of 1, 2, and 5 units, to minimize coins for m units: select the largest denomination first (local optimal), which guarantees global minimum. However, with coins 1, 2, 4, 5, 6, and a target of 9, greedy picks 6+2+1 (3 coins), while 5+4 (2 coins) is better.
2. Souvenir Grouping
Constraints: Each group holds up to 2 souvenirs, total value ≤ capacity w. Maximize space efficiency by pairing large-value items with small ones.
capacity = int(input())
souvenir_count = int(input())
values = [int(input()) for _ in range(souvenir_count)]
values.sort()
min_groups = 0
left, right = 0, souvenir_count - 1
while left <= right:
if left == right:
min_groups += 1
break
if values[left] + values[right] <= capacity:
left += 1
right -= 1
min_groups += 1
else:
right -= 1
min_groups += 1
print(min_groups)
Input & Output:
100
9
90
20
20
30
50
60
70
80
90
6
3. Flip the Coins
Goal: Transform string s to string t, flipping any two consecutive characters with each operation.
source = list(input())
target = list(input())
length = len(source)
flip_count = 0
for i in range(length - 1):
if source[i] != target[i]:
flip_count += 1
source[i + 1] = 'o' if source[i + 1] == '*' else '*'
print(flip_count)
Input & Output:
**********
o****o****
5
