主页 / 问题 / 1560558
Accepted
Alexander
Asked:2024-01-07 20:36:26 +0000 UTC2024-01-07 20:36:26 +0000 UTC

使用bitset的背包问题

  • 772

最近我了解到，为了加快解决背包问题的速度，可以使用C++中的bitset结构来进行位压缩。有一个问题：有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;
}

如果有人已经做过类似的实现，请告诉我最适合我做什么。

c++

1 个回答

  1. Best Answer

    该代码可能被错误地重写。必须在 OR 之后(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]];
        }
    }
    • 1

相关问题