Схема приближения для рюкзака: огрубить ценности, а не веса

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

Как думаешь, что можно огрубить

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

Ответь себе до чтения: что огрублять - веса или ценности? Веса кажутся очевидным кандидатом: таблица идёт по вместимости, огрубил веса - сузил таблицу. Но огрублённый вес врёт о том, поместится ли набор, и ошибка в эту сторону недопустима: рюкзак не застегнётся. Ошибка в ценности стоит денег, но не нарушает условия. Огрублять надо там, где ошибку можно оплатить.

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

Смета ремонта. Прораб считает материалы в тысячах рублей, отбрасывая сотни: на итог это влияет не больше чем на тысячу за позицию, и выбор между вариантами почти не меняется. Но размеры комнаты он меряет до сантиметра: округлишь вниз - шкаф не влезет, и никакая экономия этого не исправит.

В рюкзаке ценность - это смета, а вес - размер комнаты. Огрубление ценности стоит денег, которые можно оценить заранее. Огрубление веса ломает допустимость, и оценить этот ущерб нечем.

Механизм: таблица по ценности и шаг огрубления

Таблица по ценности. Вместо «наибольшая ценность при весе не больше w» храним «наименьший вес набора с ценностью ровно s». Ответ - наибольшее s, у которого вес не больше W. Размер таблицы - сумма ценностей, время - n · Σ v. Ценности в миллионах - таблица в миллионы столбцов.

Огрубление. Шаг K = ε · vmax / n, огрублённая ценность v'ᵢ = ⌊vᵢ / K⌋. Каждая из них не больше n / ε, сумма не больше n² / ε, и таблица работает за n³ / ε - от величины чисел время больше не зависит.

Потеря. Пусть S - набор, лучший по огрублённым ценностям, O - настоящий оптимум.

K · v'ᵢ >= vᵢ − K                 отброшено меньше одного шага
Σ_S vᵢ >= Σ_S K·v'ᵢ >= Σ_O K·v'ᵢ  S лучший по огрублённым
       >= Σ_O vᵢ − n·K = OPT − ε · vmax
       >= (1 − ε) · OPT           каждый предмет помещается один,
                                  значит, OPT >= vmax

Веса в таблице точные, поэтому набор S всегда помещается. Вся потеря - в ценности, и она ограничена заранее.

Схемы приближения. Алгоритм, который для любого ε > 0 даёт (1 − ε)-приближение (для минимума - (1 + ε)), называют схемой приближения. Если время - многочлен от n при каждом фиксированном ε, это PTAS; если многочлен и от n, и от 1/ε - FPTAS, полностью полиномиальная схема. Схема для рюкзака - FPTAS (Ибарра, Ким, 1975).

Правило

Схема приближения для рюкзака: огрубить ценности шагом K = ε · vmax / n и решить точно таблицей «наименьший вес для данной ценности». Ответ не хуже (1 − ε) · OPT, время порядка n³ / ε - это FPTAS. Веса не огрубляют: ошибка в них ломает допустимость, а не стоимость.

Разбор: двенадцать предметов и четыре точности

tochno - обычная таблица по весу (веса здесь малы, так что точный ответ доступен для сверки). shema - таблица по огрублённой ценности: legchajshij[s] - наименьший вес набора с огрублённой ценностью s, nabor[s] - сам набор.

def tochno(cennosti, vesa, W):
    luchshee = [0] * (W + 1)
    for i in range(len(vesa)):
        for w in range(W, vesa[i] - 1, -1):
            if luchshee[w - vesa[i]] + cennosti[i] > luchshee[w]:
                luchshee[w] = luchshee[w - vesa[i]] + cennosti[i]
    return luchshee[W]

def shema(cennosti, vesa, W, eps):
    n = len(cennosti)
    K = eps * max(cennosti) / n
    grubo = []
    for c in cennosti:
        grubo.append(int(c // K))
    vsego = sum(grubo)
    beskonechno = sum(vesa) + 1
    # legchajshij[s] - наименьший вес набора с огрублённой ценностью s
    legchajshij = [beskonechno] * (vsego + 1)
    nabor = [[]] * (vsego + 1)
    legchajshij[0] = 0
    for i in range(n):
        for s in range(vsego, grubo[i] - 1, -1):
            ves = legchajshij[s - grubo[i]] + vesa[i]
            if ves < legchajshij[s]:
                legchajshij[s] = ves
                nabor[s] = nabor[s - grubo[i]] + [i]
    s = vsego
    while legchajshij[s] > W:
        s = s - 1
    nastoyaschaya = 0
    for i in nabor[s]:
        nastoyaschaya = nastoyaschaya + cennosti[i]
    return [vsego, nastoyaschaya]

cennosti = [4100, 3850, 2950, 2700, 2425, 2010, 1890, 1515,
            1240, 980, 715, 430]
vesa = [41, 40, 31, 29, 27, 22, 21, 17, 15, 12, 9, 6]
W = 120
opt = tochno(cennosti, vesa, W)
print(opt)
for eps in [0.5, 0.2, 0.1, 0.05]:
    r = shema(cennosti, vesa, W, eps)
    print(eps, r[0], r[1], round(r[1] / opt, 4), r[1] >= (1 - eps) * opt)

11475
0.5 139 11365 0.9904 True
0.2 359 11475 1.0 True
0.1 720 11475 1.0 True
0.05 1446 11475 1.0 True

Столбцы: точность ε, ширина таблицы (сумма огрублённых ценностей), настоящая ценность найденного набора, отношение к оптимуму и проверка гарантии. При ε = 0,5 шаг K ≈ 171 - огрубление грубое, таблица в 139 столбцов, и набор хуже оптимума на 1% при обещанных 50%. При ε = 0,2 таблица в 359 столбцов уже находит оптимум. Без огрубления таблица по ценности была бы шириной 24 805 - сумма всех ценностей.

Ширина таблицы растёт как 1/ε: 139, 359, 720, 1446 - примерно во столько же раз, во сколько уменьшилось ε. (Почему 139, а не 140: шаг K = 170,83… хранится двоичной дробью, и 4100 / K выходит чуть меньше 24 - так считает и настоящий Python.) Это и значит «полиномиально по 1/ε»: заказать точность в десять раз выше стоит в десять раз больше времени, а не в 2¹⁰.

Разбор: что будет, если огрубить веса

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

def po_vesu(cennosti, vesa, W):
    luchshee = [0] * (W + 1)
    nabor = [[]] * (W + 1)
    for i in range(len(vesa)):
        for w in range(W, vesa[i] - 1, -1):
            c = luchshee[w - vesa[i]] + cennosti[i]
            if c > luchshee[w]:
                luchshee[w] = c
                nabor[w] = nabor[w - vesa[i]] + [i]
    return nabor[W]

def itog(nabor, cennosti, vesa):
    c = 0
    v = 0
    for i in nabor:
        c = c + cennosti[i]
        v = v + vesa[i]
    return [c, v]

cennosti = [4100, 3850, 2950, 2700, 2425, 2010, 1890, 1515,
            1240, 980, 715, 430]
vesa = [41, 40, 31, 29, 27, 22, 21, 17, 15, 12, 9, 6]
W = 120
tochnyj = po_vesu(cennosti, vesa, W)
vniz = []
vverh = []
for v in vesa:
    vniz.append(v // 10)
    vverh.append((v + 9) // 10)
print(itog(tochnyj, cennosti, vesa))
print(itog(po_vesu(cennosti, vniz, W // 10), cennosti, vesa))
print(itog(po_vesu(cennosti, vverh, W // 10), cennosti, vesa))

[11475, 120]
[15135, 166]
[10650, 110]

Точный ответ: 11 475 при весе 120. Огрубление вниз: таблица думает, что набор весит 12 «десятков», а на деле 166 килограммов при вместимости 120 - набор не помещается, и ценность 15 135 - ценность невыполнимого ответа. Огрубление вверх безопасно: набор помещается (110), но ценность 10 650 - минус 7%, и эту потерю нельзя оценить заранее, она зависит от того, сколько предметов «чуть-чуть не влезли».

Округление ценностей вниз даёт обратную картину: допустимость не задета, а потеря ограничена n · K. Это и есть «огрублять в безопасную сторону»: ошибаться можно там, где ошибку удаётся сосчитать.

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

Огрубляют веса вниз. Набор не помещается, ответ невыполним. Самая опасная ошибка, потому что число на выходе выглядит лучше оптимума.

Берут шаг от суммы, а не от наибольшей ценности. Оценка потери опирается на OPT ≥ vmax; шаг от суммы ценностей огрубляет слишком сильно, и гарантия теряется.

Не убирают предметы, которые не помещаются по одному. Тогда vmax может быть больше OPT, и шаг выходит слишком крупным. Такие предметы выбрасывают до огрубления.

Ждут точного ответа от малого ε. При ε = 0,2 здесь вышел оптимум, но это удача входа: гарантия - только (1 − ε).

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

Выбор проектов в бюджет, загрузка контейнера, распределение рекламных денег по каналам - рюкзаки с большими числами: деньги в копейках, веса в граммах. Точная таблица на таких числах не помещается в память, а перебор не заканчивается. Схема даёт ручку: «точность 1% - секунда, 0,1% - десять секунд», и обе цифры можно обещать заранее, зная только число предметов и скорость машины. А главное правило про огрубление переносится на любую задачу: огрубляй то, в чём ошибка стоит денег, и никогда то, в чём ошибка нарушает условие.

Теперь сам

1. n = 50, vmax = 1 000 000, ε = 0,1. Каков шаг K и сколько потеряет каждый предмет в худшем случае?
2. Почему в оценке потери нужно OPT ≥ vmax?
3. Ширина таблицы при ε = 0,1 - 720. Какой она станет при ε = 0,01?