Заказы для курьера
Курьер на велосипеде везёт заказы в рюкзаке, который выдерживает W граммов. В приложении висят n заказов: у каждого вес в граммах и оплата в тенге. Заказ берут целиком или не берут вовсе. Какие заказы взять, чтобы заработать как можно больше?
Если лучших наборов несколько, выведите любой.
Вход
В первой строке n и W (1 ≤ n ≤ 100, 1 ≤ W ≤ 104). Дальше n строк: вес заказа wi в граммах и оплата ci в тенге (1 ≤ wi ≤ 104, 1 ≤ ci ≤ 105). Заказы пронумерованы с единицы в порядке ввода.
Выход
В первой строке — наибольшая сумма оплаты. Во второй — сколько заказов взять. В третьей — их номера через пробел (строка пустая, если не взято ничего).
Примеры
Пример 1
4 10000 6000 1300 5000 1000 5000 1000 800 100
2000 2 2 3
Пример 2
2 500 900 2000 600 700
0 0
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Первая мысль — брать заказы по убыванию оплаты за грамм. Проверьте её на первом примере: рюкзак на 10 кг, заказ 6 кг за 1300 тенге и два заказа по 5 кг за 1000.
2Подсказка 2
Рассмотрите последний заказ. Если его не брать, ответ — лучшее из первых n − 1 заказов при том же месте. Если брать — его оплата плюс лучшее из первых n − 1 заказов в оставшемся месте. Какие ответы для этого нужно знать заранее?
3Идея
Это рюкзак 0-1. best(i, x) — наибольшая оплата из первых i заказов при x граммах места, и best(i, x) = max(best(i − 1, x), ci + best(i − 1, x − wi)). Чтобы потом назвать сами заказы, запоминаем для каждой клетки, взят ли в ней заказ i, и идём из (n, W) назад.
4Разбор
Числа удобно хранить одной строкой длины W + 1 и обновлять её справа налево: тогда best[x − w] в момент чтения ещё относится к предыдущему заказу, и каждый заказ берётся не больше одного раза. Решения «взят ли заказ i в клетке x» строка не сохранит, поэтому для них заводим отдельный битовый массив на каждый заказ — n·(W + 1) байт, около мегабайта.
Путь назад: стоим в x = W и перебираем заказы с последнего. Если в строке заказа i клетка x отмечена, заказ взят, и x уменьшается на его вес. Отметка ставится, только когда заказ улучшил клетку по сравнению с ответом без него, поэтому так получается ровно тот набор, который дал число в последней клетке.
В первом примере жадность берёт заказ на 6 кг — у него лучшая оплата за грамм, 1300 тенге, — и больше ничего крупного не влезает: 1300 + 100 = 1400. А два заказа по 5 кг дают 2000.
4+Решение
5Сложность
O(n·W) времени — миллион клеток — и O(n·W) памяти на отметки.
6Типичные ошибки
- Жадность по оплате за грамм. Не проходит первый пример.
- Одна строка слева направо. Тогда best[x − w] уже может содержать этот же заказ, и он берётся несколько раз.
- Восстановление по одной строке чисел. В конце строка хранит ответы только для всех заказов сразу, сравнивать «с заказом и без» уже не с чем: нужна вся таблица или отметки.