그리디 알고리즘 편집하기 (부분)

==예제 문제==
대표적인 예제 중 하나는 '''동전 교환 문제(Coin Change Problem)'''이다.
===예제 1: 동전 교환 문제===
주어진 동전 단위로 특정 금액을 만들 때, 최소 개수의 동전을 사용하는 문제.
====코드====
<syntaxhighlight lang="python">
def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 큰 동전부터 정렬
    num_coins = 0
    for coin in coins:
        if amount == 0:
            break
        count = amount // coin
        num_coins += count
        amount -= count * coin
    return num_coins if amount == 0 else -1  # 거슬러 줄 수 없는 경우 -1 반환

# 예제 실행
coins = [1, 5, 10, 25]
amount = 63
print(coin_change_greedy(coins, amount))
</syntaxhighlight>
 출력 결과 예시:
 6 (25x2 + 10x1 + 5x0 + 1x3)
**주의:** 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우도 있다. 예를 들어, 동전 단위가 [1, 3, 4]이고 6원을 만들 때, 그리디 알고리즘은 4+1+1(3개)로 선택하지만 최적해는 3+3(2개)이다.
===예제 2: 분할 가능 배낭 문제(Fractional Knapsack)===
배낭의 용량이 제한되어 있을 때, 가치를 최대화하도록 아이템을 선택하는 문제.
====코드====
<syntaxhighlight lang="python">
def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0

    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

# 예제 실행
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(fractional_knapsack(weights, values, capacity))
</syntaxhighlight>
 출력 결과 예시:
 7.5