Задача о рюкзаке с ограниченным числом предметов
Задача найти наилучший расклад рюкзака, зная не только веса и стоимость, но и максимальное количество каждого товара.
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 является ответом и какова база индукции?
Ответы (1 шт):
Вы почему-то не привели описание того, что хранится в a,c,k
OK, давайте посмотрим на код.
Имеется таблица, номер строки i в которой соответствует номеру товара.
Номер колонки соответствует текущему весу (общий максимум W).
Теперь перебираем возможное количество единиц i-го товара, действуют два ограничения - количества k[i] и на возможный оставшийся вес (единица весит a[i])
Сумма в dp[i][j] складывается из цены товара c[i], помноженной на количество, и суммы в ряду выше, взятой из колонки, меньшей на вес набора текущего товара. При этом выбираем лучший вариант по стоимости при использовании разных количеств текущего товара.
Таким образом, в последнем ряду будет набор стоимостей, из которых нужно выбрать максимум
Best = max(dp[n])