Задача о рюкзаке с ограниченным числом предметов

Рейтинг: -1Ответов: 1Опубликовано: 17.05.2023

Задача найти наилучший расклад рюкзака, зная не только веса и стоимость, но и максимальное количество каждого товара.

for i in range(1, n + 1):
    for j in range(0, W + 1):
        for cnt in range(min(k[i], W // a[i]) + 1):
            if a[i] * cnt <= j:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i] * cnt] + c[i] * cnt)

Я нашёл данный код в интернете и я уверен, что он работает, но я не понимаю что в массиве dp является ответом и какова база индукции?

python алгоритм динамическое-программирование
Источник: Stack Overflow на русском

Ответы

▲ 0

Вы почему-то не привели описание того, что хранится в a,c,k

OK, давайте посмотрим на код.
Имеется таблица, номер строки i в которой соответствует номеру товара.
Номер колонки соответствует текущему весу (общий максимум W).

Теперь перебираем возможное количество единиц i-го товара, действуют два ограничения - количества k[i] и на возможный оставшийся вес (единица весит a[i])

Сумма в dp[i][j] складывается из цены товара c[i], помноженной на количество, и суммы в ряду выше, взятой из колонки, меньшей на вес набора текущего товара. При этом выбираем лучший вариант по стоимости при использовании разных количеств текущего товара.

Таким образом, в последнем ряду будет набор стоимостей, из которых нужно выбрать максимум

Best = max(dp[n])