Выбор ответа Senior Динамическое программирование обновлено
Рюкзак 0/1 в одномерном массиве
Вопрос
Рюкзак 0/1 со сжатием до одномерного dp[w]. Почему внутренний цикл по весу идёт от большего к меньшему?
for (const [weight, value] of items) {
for (let w = W; w >= weight; w--) {
dp[w] = Math.max(dp[w], dp[w - weight] + value);
}
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Иначе предмет возьмётся повторно: dp[w - weight] уже обновлён. При проходе по возрастанию dp[w - weight] уже учитывает текущий предмет, и он используется повторно: это рюкзак с неограниченными предметами.
Варианты ответа
- Так быстрее: обратный цикл лучше попадает в кеш процессора
- Иначе предмет возьмётся повторно:
dp[w - weight]уже обновлёнправильный ответ - Иначе выйдем за левую границу массива при
w - weight < 0 - Порядок не важен: ответ одинаков, это вопрос стиля записи
Разбор
При проходе по возрастанию dp[w - weight] уже учитывает текущий предмет, и он используется повторно: это рюкзак с неограниченными предметами. Обратный проход читает значения с предыдущего предмета.
- Скорость одинакова.
- Границы проверяются условием цикла
w >= weight. - Порядок принципиален.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.