У вас есть N предметов с весами w 1 , w 2 , … ,...

Question

У вас есть
N
предметов с весами
w
1
,
w
2
,
…
,
w
N
. Требуется проверить, можно ли выбрать некоторые предметы, суммарный вес которых равен
W
.

Формат входных данных
В первой строке записаны два целых числа
N
и
W
(
1
≤
N
≤
2
500
,
1
≤
W
≤
6
250
000
).

Во второй строке через пробел записаны
N
целых чисел
w
1
,
w
2
,
…
,
w
N
(
1
≤
w
i
≤
2
500
) — веса предметов.

Формат выходных данных
В единственной строке выведите «YES» (без кавычек), если, используя данные предметы, можно набрать вес
W
, либо «NO» в противном случае.

Примеры
Входные данные
5 10
1 2 3 4 5
Выходные данные
YES
Входные данные
2 10
4 5
Выходные данные
NO написать код на с++ используя битовые операции

Answer 1

Для решения задачи можно использовать динамическое программирование с использованием битовых операций. Метод заключается в том, что мы будем использовать битовое представление возможных сумм, которые можно собрать из предметов. В этом решении для каждой суммы будем устанавливать соответствующий бит.

Пример кода на C++:

cpp
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, W;
    cin >> N >> W;
    
    vector<int> weights(N);
    for (int i = 0; i < N; ++i) {
        cin >> weights[i];
    }

    // Максимальный возможный вес, который мы будем учитывать
    const int MAX_W = 6250000; 
    
    // Битовый массив, где бит i означает, что вес i достижим
    vector<bool> can_make(MAX_W + 1, false);
    can_make[0] = true; // Нулевой вес всегда достижим

    for (int i = 0; i < N; ++i) {
        // Идем по весам от большого к меньшему, чтобы не учитывать один и тот же элемент дважды
        for (int j = MAX_W - weights[i]; j >= 0; --j) {
            if (can_make[j]) {
                can_make[j + weights[i]] = true;
            }
        }
    }

    if (W <= MAX_W && can_make[W]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

Пояснение:

Ввод: Считываем количество предметов и требуемую сумму. Далее считываем массив весов предметов.
Массив can_make: Этот массив будет хранить, достижим ли вес с данным индексом. Индекс массива — это возможный вес, а значение в ячейке — это логическое значение (true, если этот вес достижим, иначе false). Мы начинаем с того, что вес 0 всегда достижим (так как без предметов мы можем собрать 0).
Динамическое программирование: Для каждого предмета мы обновляем массив достижимых весов, начиная с самого большого веса и двигаясь к меньшим, чтобы не использовать один и тот же предмет несколько раз.
Проверка: В конце проверяем, достижим ли заданный вес W и выводим результат.

Время работы:

Заполнение массива достижимых весов — O(N * W), где N — количество предметов, а W — максимальный возможный вес (в нашем случае до 6.25 миллиона). Однако в практике, если W большое, но не все возможные веса будут проверяться, программа будет работать быстрее за счет ограничений на веса.

Этот алгоритм эффективно решает задачу с учетом ограничений.

У вас есть N предметов с весами w 1 , w 2 , … ,...

Question

Réflexion

Réponse

Пояснение:

Время работы:

Partager cette Q&R