Greedy

The greedy algorithm is applied to optimization problems, aiming to find the optimal solution when possible or, if not, a satisfactory solution within a limited time frame. It is particularly valuable for providing near-optimal solutions efficiently.

Problems well-suited to greedy algorithms possess two main properties: the greedy choice property and optimal substructure.

1. The greedy choice property indicates that choices made at each step are independent of previous choices; a greedy algorithm never reconsiders its options.

2. Optimal substructure implies that a problem's optimal solution comprises optimal solutions to its subproblems.

Greedy algorithms are often contrasted with dynamic programming: while dynamic programming combines optimal solutions of subproblems to solve the larger issue, greedy algorithms iteratively make locally optimal choices to incrementally build a solution.

Fractional Knapsack Problem

Calculate the greedy algorithm by unit price. In other words, the cargo with the highest unit price is placed at the top.

1. Greedy Algorithm: Suitable for the Fractional Knapsack Problem where items can be divided.

2. Dynamic Programming: Used for the 0-1 Knapsack Problem where items cannot be divided.

# (price, weight)
cargo = [(4, 12), (2, 1), (10, 4), (1, 1), (2, 2)]

def fractional_knapsack(cargo):
    capacity = 15
    pack = []
    
    # Sort in descending order of unit price
    for c in cargo:
        pack.append(c[0] / c[1], c[0], c[1]))
    pack.sort(reverse=True)
    
    # Greedy algorithm in order of unit price
    total_value: float = 0
    for p in pack:
        if capacity - p[2] >= 0:
            capacity -= p[2]
            total_value += p[1]
        else:
            fraction = capacity / p[2]
            total_value += p[1] * fraction
            break
            
    return total_value

Coin Change Problem

1. Greedy Algorithm: Effective when each coin's denomination is a multiple of the one before it.

2. Dynamic Programming: Necessary when coins have denominations like 10, 50, 80, and 100. For instance, to make change for 160, the best solution is two 80 coins instead of one 100, one 50, and one 10 coin.

Largest Sum

For the problem of finding the path with the largest sum in a binary tree, a greedy algorithm falls short because it cannot guarantee the discovery of the path with the largest sum, such as when the leftmost leaf node is part of the optimal path. Here, a greedy algorithm is not a suitable solution method.