Жадные алгоритмы
Жадные алгоритмы — это популярная группа методов, где итоговое решение формируется пошагово, и на каждом этапе выбирается наиболее очевидный или оптимальный вариант. Как правило, они довольно просты для понимания, но иногда бывает нелегко определить правильную эвристику на каждом шаге.
Задача
У вас есть рюкзак и
n предметов. Вы хотите уместить в рюкзак как можно больше предметов, но при этом знаете, что рюкзак может порваться, если суммарный вес в нем превысит некоторый порог t. Нужно определить, сколько предметов максимального количества вы сможете взять с собой так, чтобы рюкзак не порвался.Входные данные
Первая строка входных данных содержит два целых числа
n (1 ≤ n ≤ ) и t (1 ≤ t ≤ ) — количество предметов и допустимый порог для рюкзака.Во второй строке записаны
n целых чисел, разделенных пробелами: (1 ≤ ≤ ) — веса каждого из предметов.Выходные данные
Программа должна вывести максимальное количество предметов, которые можно унести.
Примеры
Input | Output |
7 10
4 1 2 5 8 7 1 | 4 |
Пояснение
Можно, например, взять
1, 2, 5, 1, или 4, 1, 2, 1, или 1, 2, 7, 1. Во всех случаях общее число предметов равно 4.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB