Рюкзак 0/1 на одномерном массиве: почему предмет берётся дважды
Классический рюкзак 0/1: каждый предмет можно взять не более одного раза.
def knapsack(weights, values, cap):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(w, cap + 1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[cap]
Вызов knapsack([3], [5], 9) возвращает 15, хотя предмет всего один и правильный ответ 5. Где ошибка?
- Внутренний цикл идёт по возрастанию, поэтому предмет берётся повторно: нужен range(cap, w - 1, -1)
- Ошибка в zip: он молча обрезает списки разной длины, из-за чего предмет обрабатывается несколько раз
- Массив dp надо инициализировать минус бесконечностью везде, кроме dp[0], иначе максимум берётся из мусора
- Одномерный dp для рюкзака 0/1 непригоден в принципе: нужна двумерная таблица по предметам и вместимости