1. 问题分析

本题是一道变型的背包问题，其核心约束与目标函数均由传统的“算术求和”转变为“位运算按位与（Bitwise AND）”。这一转变彻底改变了问题的数学完备性与贪心策略的应用边界。

核心矛盾： 在标准背包问题中，增加物品会导致总体积单调增加，而在本题中，按位与运算具有非增性（）。这意味着：

  1. 体积约束的变化：选取的物品越多，总体积反而可能越小，越容易满足 的限制。
  2. 价值目标的变化：选取的物品越多，总价值同样可能越小。

关键观察： 题目要求最大化 。 若一个最终价值 是可达成的，那么对于选中的每一个物品 ，其价值 必须在位模式上是 的超集（即 ）。

2. 算法：位掩码贪心搜索 (Bitmask Greedy Search)

由于 ，数据范围限定在 以内。我们可以避开复杂的动态规划，利用位运算的单调性采用枚举策略。

基于价值掩码的有效性校验

与其尝试构建最优组合，不如直接枚举可能的最终价值 ，并验证该价值在体积约束下是否可行。

证明：为什么只需要考虑每个掩码下“全选”的策略？ 假设目标价值至少包含掩码 的位。为了使这个目标最容易达成（即让总体积尽量小），根据按位与的性质，我们应该选择所有满足 条件的物品。

  • 将这些符合条件的物品全部进行按位与运算，得到的结果总体积 是该价值掩码下能达到的最小体积。
  • 如果这个最小体积 ，则说明目标价值 （或更高的价值）是合法的。

为什么不使用动态规划？

传统的 0/1 背包 DP 状态定义为 dp[i][v]，表示前 个物品在体积为 时的最大价值。但在位运算下，体积不具备累加性，状态转移不再满足最优子结构。若强行使用 DP，由于按位与结果的离散性，复杂度会退化至 ，不如掩码枚举高效。

3. 复杂度分析

  • 时间复杂度：

    • 为数值的上界（本题为 ）。
    • 为物品数量（）。

  • 空间复杂度：

    • 仅需存储物品的 和 数组，空间消耗极低。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    const int M = 2048;
    vector<int> v(n), w(n);
    for (int i = 0; i < n; i++)
        cin >> v[i] >> w[i];

    for (int mask = M - 1; mask >= 0; mask--) {
        bool found = false;
        int curV = -1;

        for (int j = 0; j < n; j++) {
            // 如果物品价值 w[j] 包含当前 mask 所有的 1 位
            if ((w[j] & mask) == mask) {
                if (found) {
                    curV &= v[j];
                } else {
                    curV = v[j];
                    found = true;
                }
            }
        }

        if (found && curV <= k) {
            cout << mask << endl;
            return 0;
        }
    }

    cout << 0 << endl;
    return 0;
}