Проекты для района
Район выбирает, какие дворы благоустроить в этом году. Есть n проектов: проект i стоит ci тенге и приводит в порядок vi дворов. Проект либо делают целиком, либо не делают, а один двор не входит в два проекта. Бюджет — B тенге. Сколько дворов можно благоустроить за эти деньги?
Вход
В первой строке n и B (1 ≤ n ≤ 100, 0 ≤ B ≤ 1011). Дальше n строк: стоимость проекта ci в тенге и число дворов vi (1 ≤ ci ≤ 109, 1 ≤ vi ≤ 100).
Выход
Наибольшее число дворов, которое можно благоустроить, не выходя из бюджета.
Примеры
Пример 1
4 1000 600 13 500 10 500 10 80 1
20
Пример 2
2 50 90 5 60 3
0
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это рюкзак: бюджет — вместимость, стоимость — вес, дворы — польза. Сколько клеток будет в обычной таблице «первые i проектов, b тенге», если бюджет — сто миллиардов?
2Подсказка 2
Какая величина во входе маленькая? Дворов у проекта не больше ста, а проектов не больше ста. Что если столбцами таблицы сделать не деньги, а дворы?
3Идея
Повернём таблицу: cheapest[v] — наименьшие деньги, за которые можно благоустроить ровно v дворов. Дворов всего не больше 100 · 100 = 104, и таблица маленькая, сколько бы ни стоили проекты. Переход тот же, что в рюкзаке 0-1, только с минимумом: cheapest[v] = min(cheapest[v], cheapest[v − vi] + ci). Ответ — наибольшее v, для которого cheapest[v] ≤ B.
4Разбор
Вначале cheapest[0] = 0, остальные — бесконечность: ни один проект ещё не рассмотрен. Проекты добавляем по одному, проходя массив от больших v к меньшим, чтобы проект не учитывался дважды. Суммы денег доходят до 1011: в Go нужен int64, и «бесконечность» стоит брать с запасом, чтобы прибавление стоимости к ней не переполнило число.
Вспомните псевдополиномиальность: время рюкзака зависит от величины чисел в той размерности, по которой строится таблица. Обычно это вместимость, но строить таблицу можно по любой из двух величин — по весу или по ценности. Выбираем ту, где числа маленькие.
4+Решение
5Сложность
O(n · Σvi) — не больше 106 шагов — и O(Σvi) памяти.
6Типичные ошибки
- Таблица по деньгам. Сто миллиардов клеток не помещаются в память. Проходит только примеры.
- Жадность по дворам на тенге. Не проходит первый пример — тот же подвох, что в обычном рюкзаке.
- Переполнение. Сумма стоимостей ста проектов — до 1011, в 32 бита не помещается.