1. Идея

Нужно выбрать как можно больше предметов так, чтобы их общий вес не превышал W.

Если хочется взять максимальное количество предметов, то выгодно брать самые лёгкие предметы. Тогда на тот же лимит веса поместится больше вещей, чем если начинать с тяжёлых.

Значит, задача сводится к очень простой жадной стратегии:

• отсортировать веса по возрастанию;
• идти слева направо;
• пока очередной предмет помещается, брать его;
• как только очередной предмет уже не помещается, дальше смысла проверять нет.

2. Наблюдения

Наблюдение 1

Если среди выбранных предметов есть тяжёлый предмет, а вне выбора есть более лёгкий, то заменить тяжёлый на лёгкий никогда не хуже:

• суммарный вес не увеличится;
• количество предметов останется тем же.

Значит, среди оптимальных ответов всегда существует такой, где взяты самые лёгкие предметы.

Наблюдение 2

После сортировки веса идут в порядке:

a[0] <= a[1] <= ... <= a[n-1]

Если мы не можем взять предмет a[i], то любой следующий предмет a[i+1], a[i+2], ... тоже не сможем взять, потому что они не легче.

Поэтому после первого же "не влезает" можно сразу остановиться.

Наблюдение 3

Ограничение на W очень большое: до 10^18, поэтому сумму нужно хранить в 64-битном типе:

• в C++ это long long;
• в Python обычный int подходит автоматически.

3. Алгоритм

1. Считать n и W.
2. Считать массив весов a.
3. Отсортировать a по возрастанию.
4. Завести:
   • sum = 0 — текущая сумма весов;
   • answer = 0 — сколько предметов уже взяли.
5. Для каждого веса x в отсортированном массиве:
   • если sum + x <= W, то:
     • добавить предмет: sum += x;
     • увеличить answer.
   • иначе остановиться.
6. Вывести answer.

4. Почему это работает

Докажем, что описанный жадный алгоритм действительно находит максимальное количество предметов.

После сортировки рассмотрим первые k самых лёгких предметов. Их суммарный вес минимален среди всех наборов из k предметов.

Почему это так? Потому что любой другой набор из k предметов содержит предметы не легче соответствующих первых k элементов отсортированного массива. Значит, сумма у такого набора не меньше.

Теперь посмотрим на работу алгоритма:

• он берёт подряд самые лёгкие предметы, пока хватает лимита;
• пусть он смог взять k предметов, но k + 1-й уже не помещается.

Это означает, что сумма первых k + 1 самых лёгких предметов больше W.

Но тогда любой набор из k + 1 предметов тоже будет иметь сумму не меньше, а значит, тоже не поместится.

Следовательно:

• взять k + 1 предметов невозможно;
• k — это максимально возможное число предметов.

Значит, алгоритм корректен.

5. Сложность

Основное время тратится на сортировку:

• сортировка: O(n log n)
• проход по массиву: O(n)

Итоговая сложность: O(n log n)

Память:

• массив весов: O(n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    long long W;
    cin >> n >> W;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long sum = 0;
    int answer = 0;

    for (int i = 0; i < n; i++) {
        if (sum + a[i] <= W) {
            sum += a[i];
            answer++;
        } else {
            break;
        }
    }

    cout << answer << "\n";
    return 0;
}

7. Код на Python 3

n, W = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

s = 0
answer = 0

for x in a:
    if s + x <= W:
        s += x
        answer += 1
    else:
        break

print(answer)