Жадные алгоритмы и DP: когда что использовать

Обзор жадных алгоритмов и DP

# Greedy: always take the locally best option
# Example: coin change with coins [1, 5, 10, 25]
# Greedy: take as many 25s as possible, then 10s, etc.
# This works for standard denominations but NOT all coin sets!

# DP: explore all possibilities via memoisation
# Example: coin change with coins [1, 3, 4] and target 6
# Greedy would pick 4, then 1, 1 → 3 coins
# DP finds: 3 + 3 → 2 coins (optimal!)
print('Greedy can fail when local optimum != global optimum')

Свойство жадного выбора

# Exchange argument example: Activity Selection
# Greedy: always pick the activity that ends earliest
# Proof: suppose optimal solution starts with activity A (not earliest-ending)
# Let G be the earliest-ending activity.
# Replace A with G in the solution:
# - G ends no later than A, so G does not conflict with any activity A allowed
# - The solution remains valid with at least as many activities
# Therefore greedy choice (earliest end) is always safe.

activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)]
activities.sort(key=lambda x: x[1])  # sort by end time
print('Sorted by end:', activities[:4], '...')

Оптимальная структура подзадач

# Greedy works: activity selection
# Making the greedy choice (earliest-ending) leaves a sub-problem
# that is structurally identical (activity selection on remaining activities)
# and the greedy choice for the sub-problem is still valid.

# DP needed: 0/1 knapsack
# After choosing to include/exclude item i, the remaining sub-problem
# depends on WHICH item we chose — different choices yield different sub-problems.
# No single greedy rule works for all inputs.

print('Greedy: sub-problem is unique after each choice')
print('DP: sub-problem depends on which choice was made')

Перекрывающиеся подзадачи как признак DP

# Recursion tree for coin change [1,3,4], target=6
# bt(6) → bt(5) → bt(4) → bt(3) (repeated!)
#              → bt(2) → bt(1) (repeated!)
#         → bt(3) (repeated!)
#       → bt(2) (repeated!)

# Without memoisation: exponential time
# With DP table: O(target * len(coins)) time

def coin_change_dp(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change_dp([1, 3, 4], 6))  # 2 (3+3)
print(coin_change_dp([2], 3))        # -1 (impossible)

Классические задачи для жадных алгоритмов

# Fractional Knapsack: greedy works
def fractional_knapsack(items, capacity):
    # Sort by value/weight ratio descending
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    total = 0
    for weight, value in items:
        if capacity <= 0: break
        take = min(weight, capacity)
        total += take * (value / weight)
        capacity -= take
    return total

items = [(10, 60), (20, 100), (30, 120)]  # (weight, value)
print(fractional_knapsack(items, 50))  # 240.0

# 0/1 Knapsack: greedy FAILS
# Must use DP (can't take fractions)

Когда жадный подход не работает: контрпримеры

# Counterexample: coin change with non-standard coins
def greedy_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for c in coins:
        while amount >= c:
            amount -= c
            count += 1
    return count if amount == 0 else -1

def dp_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a-c] + 1)
    return dp[amount] if dp[amount] < float('inf') else -1

coins, target = [1, 3, 4], 6
print('Greedy:', greedy_coins(coins[:], target))  # 3 (4+1+1)
print('DP:    ', dp_coins(coins, target))          # 2 (3+3)

Сравнительная таблица: жадные алгоритмы и DP

# Performance comparison
import time

def time_it(func, *args):
    start = time.time()
    result = func(*args)
    return result, time.time() - start

# Large coin change test
coins = [1, 5, 10, 25, 100]
amount = 10000

def dp_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a-c]+1)
    return dp[amount]

result, elapsed = time_it(dp_coins, coins, amount)
print(f'DP coin change(amount={amount}): {result} coins in {elapsed:.4f}s')

Схема принятия решения

# Decision questions to ask:
questions = [
    '1. Is there a natural ordering (by time, ratio, size)?',
    '2. Does making the greedy choice leave a smaller same-type problem?',
    '3. Can I construct a counterexample quickly?',
    '4. Are sub-problems reused across different choice sequences?',
    '5. Does the problem involve counting or listing (not just optimising)?',
]
for q in questions:
    print(q)

print()
print('Greedy signals: scheduling, spanning tree, Huffman, jump game')
print('DP signals: knapsack, edit distance, LCS, coin change (general)')

Задачи на интервалы: жадные алгоритмы и DP

# Non-overlapping intervals: greedy works
def erase_overlap_intervals(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            last_end = end  # keep this interval
        else:
            count += 1  # remove this interval
    return count

print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))        # 2

Распознавание признаков задачи

# Signal-to-algorithm mapping
signals = {
    'minimum steps/coins/operations': 'DP (unless trivially greedy)',
    'maximum profit/value with constraint': 'DP (knapsack family)',
    'count ways to reach/achieve': 'DP (always)',
    'all combinations/permutations': 'Backtracking',
    'schedule tasks within time': 'Greedy (sort by deadline/end)',
    'cannot pick adjacent': 'DP (house robber pattern)',
    'free to pick any subset': 'DP or Greedy (check overlap)',
    'interval merging/selecting': 'Greedy (sort by end time)',
}
for signal, algo in signals.items():
    print(f'{signal!r}: → {algo}')

Доказательство корректности жадного алгоритма

# Exchange argument demo: earliest-finish-time activity selection
# Suppose OPT starts with activity A (not earliest-ending)
# Let G = earliest-ending activity available
# A.end >= G.end (G ends earlier or same time)

# Swap A for G in OPT:
# - G.end <= A.end, so G does not conflict with anything A allowed after it
# - OPT remains valid with the same number of activities
# - Repeat: after swap, OPT begins with G, matching greedy first choice
# By induction, OPT can be transformed to match G activity by activity
# without losing activities → greedy is optimal

print('Exchange argument: any OPT can be modified to match Greedy without loss')
print('This proves Greedy >= OPT in objective value')

Быстрая проверка

Итоги урока