Трюм корабля: рюкзак, жадность и граница таблицы

Если ты помнишь, когда рюкзак решается жадно, а когда только динамикой, и чем опасна таблица по весу, листай до «Теперь сам».

Как думаешь, что взять в трюм

В трюме 10 единиц места. Ящик пряностей весит 6 и стоит 30 - по 5 за единицу веса. Ящики шёлка и чая весят по 5 и стоят по 24 - по 4,8. Что взять?

Ответь себе до чтения. Первое движение - брать самое дорогое за единицу веса: пряности, 30. После них осталось 4 места, ни шёлк, ни чай не влезают. Итого 30. А шёлк и чай вместе - ровно 10 места и 48 цены. Жадность взяла лучший ящик и заперла себе трюм. Будь это зерно, которое можно отсыпать, жадность взяла бы пряности и 4/5 мешка шёлка - 49,2, - и это было бы верно.

На что это похоже

Сборы в поход с жёстким лимитом багажа. Если всё делится - вода, крупа, - кладёшь сначала самое полезное на килограмм и досыпаешь до предела. Если вещи целые - палатка, спальник, котелок, - лучшая по пользе на килограмм вещь может не оставить места для двух чуть менее полезных, которые вместе дают больше.

Механизм: таблица по весу и где она кончается

Динамика из раздела 15: t[w] - лучшая цена набора весом не больше w из уже рассмотренных ящиков. Новый ящик весом v и ценой c либо не берут - t[w] прежний, - либо берут - тогда t[w − v] + c. Берётся большее. Чтобы ящик не попал в набор дважды, w перебирают сверху вниз: t[w − v] к этому моменту ещё «старый», без нового ящика. Работа - n · W клеток: ящиков на вместимость.

Это псевдополиномиальное время из раздела 21: оно полиномиально по ВЕЛИЧИНЕ W, но не по длине её записи. Вместимость 40 - таблица в 41 клетку. Вместимость 40 тонн в килограммах - 40 001 клетка на ящик, и это ещё нормально. В граммах - сорок миллионов на ящик, и таблица не помещается ни в бюджет хода, ни в память. Тогда выручает приближённая схема из раздела 22: цены огрубляют, таблицу строят по цене, и ответ гарантированно не хуже (1 − ε) оптимума.

Жадность по цене за единицу веса верна для дробного рюкзака - когда груз делится. Доказательство - обменом из раздела 14: если в оптимуме есть дешёвый за килограмм груз, а дорогой взят не весь, замена килограмма дешёвого на килограмм дорогого только улучшает ответ. На целых ящиках обмен не работает: килограмм ящика не заменить.

Правило

Трюм с целыми ящиками - рюкзак 0/1: динамика по весу за n · W, жадность по цене за килограмм не гарантирует ничего. Груз, который можно делить, - дробный рюкзак: жадность точна. Таблица растёт с величиной вместимости, а не с длиной её записи - при мелких единицах веса нужно приближение.

Разбор: одиннадцать ящиков, трюм на 40

Ящики со случайным весом от 3 до 15 и ценой от 5 до 60. Сравниваем полный перебор с динамикой.

import random

random.seed(12)
gruzy = []                         # [вес, цена] - ящики с товаром
for i in range(11):
    gruzy.append([random.randint(3, 15), random.randint(5, 60)])
TRYUM = 40                         # вместимость трюма

def perebor():
    # все 2ⁿ наборов ящиков: бит i маски - берём ли ящик i
    luchshaya = 0
    naborov = 0
    for maska in range(2 ** len(gruzy)):
        ves = 0
        cena = 0
        for i in range(len(gruzy)):
            if (maska >> i) & 1:
                ves = ves + gruzy[i][0]
                cena = cena + gruzy[i][1]
        naborov = naborov + 1
        if ves <= TRYUM:
            luchshaya = max(luchshaya, cena)
    return [luchshaya, naborov]

def dinamika():
    # t[w] - лучшая цена при весе не больше w из уже рассмотренных
    # ящиков; w идёт сверху вниз, чтобы ящик не взять дважды
    t = [0] * (TRYUM + 1)
    kletok = 0
    for g in gruzy:
        for w in range(TRYUM, g[0] - 1, -1):
            kletok = kletok + 1
            t[w] = max(t[w], t[w - g[0]] + g[1])
    return [t[TRYUM], kletok]

print("ящики [вес, цена]:", gruzy[:4])
print("                  ", gruzy[4:8])
print("                  ", gruzy[8:])
print("перебор: ", perebor(), "- [цена, наборов]")
print("динамика:", dinamika(), "- [цена, клеток таблицы]")

ящики [вес, цена]: [[10, 22], [13, 38], [13, 27], [5, 29]]
                   [[3, 28], [10, 22], [13, 56], [10, 49]]
                   [[12, 19], [11, 5], [13, 44]]
перебор:  [177, 2048] - [цена, наборов]
динамика: [177, 338] - [цена, клеток таблицы]

Оба нашли 177. Перебор проверил 2048 наборов, и каждый - сложением до 11 весов. Динамика сделала 338 обновлений в таблице из 41 клетки: на каждый ящик - от вместимости 40 вниз до его веса. Двенадцатый ящик удвоил бы перебор и добавил бы динамике ещё около 30 клеток - экспонента против линии. Граница правила: обе программы печатают только цену. Перебору набор узнать легко - запомнить лучшую маску, - а динамике нет. Сам набор восстанавливают обратным ходом по таблице, а для этого её хранят целиком, n × W, а не одной строкой.

Разбор: жадность на ящиках и на зерне

Те три груза из начала урока, трюм на 10. Жадность по цене за единицу веса - на целых ящиках и на грузе россыпью - и точный ответ динамикой.

TRYUM = 10

def po_cene_za_kg(g):
    # ключ сортировки: цена за килограмм, от дорогих к дешёвым
    return -g[1] / g[0]

def zhadno(gruzy, drobno):
    # берём самое дорогое за килограмм, пока влезает; drobno=True -
    # груз можно отсыпать частью (зерно), False - ящик целиком или никак
    mesto = TRYUM
    cena = 0
    for g in sorted(gruzy, key=po_cene_za_kg):
        if g[0] <= mesto:
            mesto = mesto - g[0]
            cena = cena + g[1]
        elif drobno and mesto > 0:
            cena = cena + g[1] * mesto / g[0]
            mesto = 0
    return cena

def tochno(gruzy):
    t = [0] * (TRYUM + 1)
    for g in gruzy:
        for w in range(TRYUM, g[0] - 1, -1):
            t[w] = max(t[w], t[w - g[0]] + g[1])
    return t[TRYUM]

# [вес, цена]: пряности 5 за кг, шёлк и чай по 4,8 за кг
gruzy = [[6, 30], [5, 24], [5, 24]]
print("ящики целиком: жадно", zhadno(gruzy, False), "| точно",
      tochno(gruzy))
print("зерно россыпью: жадно", zhadno(gruzy, True))

ящики целиком: жадно 30 | точно 48
зерно россыпью: жадно 49.2

На целых ящиках жадность взяла пряности и упёрлась: 30 против 48. Ошибка не в «плохой» эвристике - любой порядок жадного выбора можно обмануть подобранными весами, задача NP-трудна. На грузе россыпью та же жадность взяла пряности целиком и 4/5 шёлка - 49,2, - и это оптимум: дробный рюкзак жадность решает точно. Граница правила: «дробность» - свойство груза, а не алгоритма. Если в трюме и ящики, и зерно, задача снова трудная. Сначала выбрать ящики, а потом досыпать зерно нельзя: ящик весом 10 и ценой 20 вытеснит зерно на 100. Перебирают, сколько места оставить зерну, и для каждого варианта ящики считают динамикой, а оставленное место досыпают жадно.

Что ломается без этого

Жадный автопогрузчик. Кнопка «загрузить лучшее» в игре берёт самое дорогое за килограмм, и опытные игроки грузят вручную на треть выгоднее. Сообщество пишет гайд «не пользуйтесь автопогрузкой».

Таблица по граммам. Вес перевели в граммы ради точности - и расчёт трюма занял секунды и сотни мегабайт.

Жадность там, где можно было. Для зерна написали динамику по граммам, хотя жадность была точна и стоила сортировку.

Зачем это в работе

Рюкзак 0/1 - это выбор задач в спринт под объём команды, раскладка рекламного бюджета по кампаниям, отбор файлов в резервную копию на носитель. Каждый раз первый вопрос - делится ли «груз»: часы работы делятся, задачи - обычно нет. Ответ на него выбирает между сортировкой и таблицей.

Теперь сам

1. Трюм на 15, ящики [вес, цена]: [7, 20], [8, 22], [5, 15], [6, 21]. Что возьмёт жадность по цене за единицу веса и каков оптимум?
2. Вместимость трюма 2000 кг, ящиков 300. Сколько клеток у таблицы динамики, если вес в килограммах? В граммах?
3. Почему в динамике w перебирают сверху вниз?