Нашли ошибку?

Специи на развес

СредняяДописатьГлава 8

#жадные алгоритмы#дробный рюкзакid: ga-bulk-spices

В лавке специи продаются на развес. У каждой специи есть доступный запас weight (граммы) и ценность этого запаса value. В сумку помещается capacity грамм. Специю можно взять целиком или частично — ценность пропорциональна весу. Допишите max_value(spices, capacity): функция возвращает максимальную суммарную ценность. Пропуски помечены # TODO.

Пример

spices = [("шафран", 10, 600), ("перец", 50, 500), ("корица", 40, 160)]
max_value(spices, 60)   # 1100.0: весь шафран (600) + 50 г перца (500)
max_value(spices, 30)   # 800.0: весь шафран + 20 г перца

Детали

Решение

def max_value(spices: list[tuple[str, int, int]], capacity: int) -> float:
    """Максимальная ценность, если специи можно брать частями."""
    # TODO: упорядочьте специи по ценности за грамм — от самой ценной
    order = list(spices)
    total = 0.0
    room = capacity
    for name, weight, value in order:
        if room <= 0:
            break
        # TODO: возьмите специю целиком, если влезает, иначе — часть, заполняющую остаток места
        pass
    return total

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 bulk_spices.py — тесты те же, результат покажет ✓ / ✗ и итог.