0/1 Knapsack Problem

Q: Как узнать, какие предметы были выбраны для задачи о рюкзаке 0/1?

Сохрани полную таблицу и двигайся назад, начиная с best[n][capacity] . Если best[i][c] отличается от best[i-1][c] , значит, предмет i-1 был упакован, поэтому запиши его и вычти его вес из c . В противном случае перейди к строке i-1 , оставив то же значение c .

СреднеДинамическое программирование

+10

У вас есть n предметов. Предмет i весит weights[i] и стоит values[i]. Ваша сумка выдерживает общий вес не более capacity. Каждый предмет существует в единственном экземпляре, и вы либо кладёте его целиком, либо оставляете. Верните наибольшую общую стоимость, которую можно унести.

Функция

knapsack(weights: integer-array, values: integer-array, capacity: integer) → integer

weightsinteger-array: вес каждого элемента
valuesinteger-array: значение каждого элемента
capacityinteger: максимальный вес, который может выдержать сумка
Возвращаетinteger: наибольшая суммарная стоимость предметов, вес которых не превышает вместимость

Ограничения

1 ≤ n ≤ 100, где n = weights.length = values.length
1 ≤ weights[i] ≤ 1000
1 ≤ values[i] ≤ 10⁴
1 ≤ capacity ≤ 1000

Примеры

Ввод: weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
Вывод: 17
Пояснение: Предметы 0 и 2 весят 4 + 3 = 7 и стоят 10 + 7 = 17. Если сначала упаковать самый ценный предмет (вес 5, ценность 12), останется место только для предмета 1, в результате получится 16.

Дополнительный вопрос

Предположим, вместимость может достигать 10^9, а сумма значений — не более 10^4. По чему вы бы индексировали таблицу?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Жадный порядок не работает: если сначала упаковать самый ценный предмет, в первом примере получится 16, а не 17. Наилучшая ценность, которую можно получить от предмета i, зависит только от i и оставшегося места — целого числа до 1000. Одна ячейка таблицы на каждую пару даёт O(n × capacity), и достаточно одной строки, если проходить значения вместимости в порядке убывания.

Попробуй оба варианта для каждого пункта

Верно, но не успевает на самых больших тестах

Идея

Пусть best(i, room) — это максимальная суммарная ценность предметов, начиная с i, которые можно добавить, если свободно room единиц вместимости; после последнего предмета значение равно 0. Пропуск предмета i дает best(i+1, room). Если предмет помещается, то есть weights[i] ≤ room, его добавление дает values[i] + best(i+1, room-weights[i]). Выбираем большее значение. Каждому варианту упаковки, который помещается, соответствует последовательность решений — упаковать предмет или пропустить его, — и рекурсия перебирает их все.

Каждый предмет удваивает число путей. Если все 100 предметов помещаются вместе, как в случае, когда каждый весит 10, а вместимость сумки равна 1000, это 2^100 путей.

Алгоритм

Напишите best(i, room); возвращайте 0, когда i выходит за пределы последнего предмета.
Присвойте skip значение best(i+1, room).
Если weights[i] > room, верните skip.
В противном случае верните большее из skip и values[i] + best(i+1, room-weights[i]).
Верните best(0, capacity).

def knapsack(weights, values, capacity):
    n = len(weights)

    # The most value items i, i+1, ... can add with room units of weight left
    def best(i, room):
        if i == n:
            return 0
        skip = best(i + 1, room)
        if weights[i] > room:
            return skip
        take = values[i] + best(i + 1, room - weights[i])
        return max(skip, take)

    return best(0, capacity)

Заполните таблицу по предметам и вместимости

Идея

Рекурсия проходит через одну и ту же пару (i, room) по множеству путей. Всего есть не более 101 × 1001, то есть около 10^5 пар, поэтому вычислим каждую из них один раз.

Пусть best[i][c] — максимальная ценность, которую первые i предметов могут поместить в рюкзак вместимости c; строка 0 целиком состоит из 0. Если предмет i-1 имеет вес w и ценность v, то, если не брать его, получится best[i-1][c], а если положить его в рюкзак, когда w ≤ c, получится best[i-1][c-w] + v. Строка i использует только строку i-1, поэтому каждый предмет учитывается в ячейке не более одного раза.

В первом примере предмет 2 (вес 3, ценность 7) повышает ценность для вместимости 7 до best[2][4] + 7 = 17. Затем предмет 3 предлагает только best[3][2] + 12 = 16, поэтому ответ остаётся равным 17.

Алгоритм

Создай таблицу из n+1 строк и capacity+1 столбцов, заполненную нулями.
Для каждой строки i от 1 до n возьми w = weights[i-1] и v = values[i-1].
Для каждой вместимости c установи best[i][c] равным best[i-1][c].
Если w ≤ c и best[i-1][c-w] + v больше, сохрани это значение.
Верни best[n][capacity].

def knapsack(weights, values, capacity):
    n = len(weights)
    # best[i][c]: the most value from the first i items within capacity c
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]  # leave item i-1 out
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v  # put it in
    return best[n][capacity]

Одна строка, ёмкости обходятся сверху вниз

Идея

Строке i нужна только строка i-1, поэтому оставьте одну строку best[c] и перезаписывайте её для каждого предмета. От направления прохода зависит, будет ли ответ правильным.

При проходе по c снизу вверх значение best[c-w] может уже включать текущий предмет. Если есть один предмет весом 3 и стоимостью 5, а вместимость равна 6, то вместимость 3 даёт стоимость 5, после чего вместимость 6 считывает это значение и становится равной 10: предмет учтён дважды. При проходе сверху вниз от capacity до w считываемая ячейка находится ниже записываемой и будет перезаписана позже, поэтому в ней всё ещё хранится значение из предыдущей строки.

Проход снизу вверх — правильный цикл, когда предметы можно брать неограниченное количество раз. Здесь время выполнения остаётся O(n × capacity), а объём памяти сокращается до одной строки.

Алгоритм

Создай best с capacity + 1 элементами, все равными 0.
Для каждого предмета с весом w и ценностью v перебирай c от capacity до w в обратном порядке.
Если best[c-w] + v больше, чем best[c], сохрани это значение в best[c].
Верни best[capacity].

def knapsack(weights, values, capacity):
    # best[c]: the most value from the items seen so far within capacity c
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Walk the capacities downward so each item goes in at most once
        for c in range(capacity, w - 1, -1):
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
    return best[capacity]

Ловушки и крайние случаи

Перебор вместимости по возрастанию в варианте с одной строкой учитывает предмет дважды: один предмет весом 3 и ценностью 5 в рюкзаке вместимостью 6 даёт результат 10 вместо 5.
Строка из capacity элементов вместо capacity + 1. Возврат best[capacity-1] приводит к потере любого варианта укладки, при котором рюкзак заполняется ровно, например предмета весом 1 в рюкзаке вместимостью 1.
Инициализация элементов значением минус бесконечность. Рюкзак не обязательно должен быть полным, поэтому каждый элемент изначально равен 0; при минус бесконечности третий пример возвращает минус бесконечность вместо 0.
Предмет тяжелее рюкзака нужно пропустить. В третьем примере замкнутый диапазон w...capacity останавливает программу в Swift, а (w+1):(capacity+1) выполняет перебор в обратном направлении в R.

Частые вопросы3

Какова временная сложность задачи о рюкзаке 0/1?

Табличный алгоритм работает за время O(n × capacity), примерно за 10^5 шагов для 100 предметов и вместимости 1000, а версия с одной строкой использует O(capacity) памяти. Эта оценка является псевдополиномиальной: она растёт вместе со значением вместимости, а не с количеством её цифр. Общая задача является NP-трудной.

Почему жадный алгоритм не работает для задачи о рюкзаке 0/1?

Жадный алгоритм никогда не отменяет сделанный выбор, даже если оставшееся место ничем не заполнить. При вместимости 7 предмет весом 5 и ценностью 10 имеет такое же наилучшее отношение ценности к весу, как и другие предметы, однако предметы весом 4 и 3 вместе стоят 13. Жадный алгоритм по отношению ценности к весу оптимален только для задачи о дробном рюкзаке, где предметы можно делить.

Как узнать, какие предметы были выбраны для задачи о рюкзаке 0/1?

Сохрани полную таблицу и двигайся назад, начиная с best[n][capacity]. Если best[i][c] отличается от best[i-1][c], значит, предмет i-1 был упакован, поэтому запиши его и вычти его вес из c. В противном случае перейди к строке i-1, оставив то же значение c.

def knapsack(weights, values, capacity):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

weights = [4, 2, 3, 5]
values = [10, 4, 7, 12]
capacity = 7

Ожидаемый вывод

0/1 Knapsack Problem

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуй оба варианта для каждого пункта

Заполните таблицу по предметам и вместимости

Одна строка, ёмкости обходятся сверху вниз

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи