Задача о рюкзаке с использованием bitset

Question

Недавно узнал, что для ускорения решения задачи о рюкзаке можно применить битовое сжатие с использованием структуры bitset в C++. Есть задача: Существует N предметов с весами w. Надо проверить, можно ли выбрать какое-то количество предметов: суммарный вес которых равен Weight. Вроде бы ничего трудного, но проблема в ограничениях: N <= 2500 и Weight <= 6250000. Увы я не особо понимаю как работает bitset в C++, поэтому не могу реализовать решение с такими ограничениями. Нашёл решение в интернете буквально такой же задачи, но понять почему оно не работает у меня не получилось:

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
 
int main() {
    int N, W;
    cin >> N >> W;
    vector<int> w(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i];
    }
    //vector<bool> A(W + 1);
    bitset<6250001> A;
    A[0] = true;
    for (int i = 1; i <= N; i++) {
        for (int j = W; j >= 0; j--) {
            if (j >= w[i - 1]) {
                A[j] = A[j] | (A[j] << w[i - 1]);
            }
        }
    }
    if (A[W]) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

Если вдруг кто уже делал подобную реализацию подскажите, пожалуйста, что мне лучше сделать.

Answer 1

Вероятно, неверно переписали код. Должно быть после ИЛИ (A[j - w[i]]), что означает, что вес j можно составить из веса w[i] и j - w[i], если последний существует (возможен).

Кроме того, я изменил нумерацию по i на нормальную (на работу это не влияет, просто нелепо)

 for (int i = 0; i < N; i++) {
        for (int j = W; j >= w[i]; j--) {
                A[j] = A[j] | A[j - w[i]];
        }
    }

БЛОГ НА HUSL

Задача о рюкзаке с использованием bitset

Ответы (1 шт):