题解 | 小苯的01背包（easy）

#include<bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5;

int n, k;
int v[N], w[N];
int f[N];

bool vis[N][N];

vector<int> V;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    int K = 0;
    for(int i = 1; i <= n; i++) cin>>v[i]>>w[i], K = max(K, v[i]);
    int I = 1;
    for(int i = 0; i <= n; i++) vis[i][0] = true;
    for(int i = 1; i <= n; i++) {
        f[v[i]] = max(f[v[i]], w[i]);
        for(int j = w[i]; j > 0; j = (j - 1) & w[i]) {
            if(!vis[v[i]][j]) {
                vis[v[i]][j] = true;
            }
        }
        for(int j = K; j >= 0; j--)
            for(int t = w[i]; t > 0 ; t = (t - 1) & w[i]) 
                if(vis[j][t]) {
                    f[j & v[i]] = max(f[j & v[i]], t);
                    if(!vis[j & v[i]][t]) {
                        vis[j & v[i]][t] = true;
                    }
                }
    }
    int maxn = 0;
    for(int i = 0; i <= k; i++) maxn = max(maxn, f[i]);
    cout<<maxn;
    return 0;
}