小苯的01背包（easy）【牛客tracker 每日一题】

小苯的01背包（easy）

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

注：此版本为本题的easy（简单版），与hard（困难版）唯一的不同之处只有数据范围。

小苯有一个容量为k kk的背包，现在有n nn个物品，每个物品有一个体积v vv和价值w ww，他想知道在体积不超过k kk的前提下，他最多能装价值为多少的物品。

本问题中，物品的总体积定义为所装物品的体积的& \&&（按位与），总价值也定义为所装物品的价值的& \&&（按位与）。

（如果不选物品，则价值为0 00，所占体积也为0 00。）

输入描述：

输入包含n + 1 n+1n+1行。
第一行两个正整数n , k ( 1 ≤ n ≤ 2 × 10 3 , 0 ≤ k ≤ 2 × 10 3 ) n,k (1≤n≤2×10^3,0≤k≤2×10^3)n,k(1≤n≤2×103,0≤k≤2×103)，分别表示物品个数和背包容量。
加下来n nn行，每行两个正整数v i , w i ( 0 ≤ v i , w i ≤ 2 × 10 3 ) v_i,w_i (0≤v_i,w_i≤2×10^3)vi​,wi​(0≤vi​,wi​≤2×103)，表示每个物品的体积和价值。

输出描述：

输出包含一行一个整数，表示能装的最大价值。

示例1

输入：

3 1 7 3 10 7 9 6

输出：

2

说明：

选择第一个和第三个物品。
体积为：7 & 9 = 1 7 \& 9=17&9=1。
价值为：3 & 6 = 2 3 \& 6=23&6=2。可以证明不存在比2 22更大的价值。

示例2

输入：

3 2 7 3 10 7 9 6

输出：

3

说明：

选择第一个和第二个物品。

解题思路

本题核心是按位贪心枚举+按位与性质验证，解决特殊规则的背包问题。利用按位与运算的单调性：选取的物品越多，价值与体积的按位与结果只会不变或变小，因此采用从大到小枚举目标价值的策略。对于每个枚举的价值，筛选出所有价值按位与能保留该值的物品，计算这些物品体积的按位与结果，若结果≤ ≤≤背包容量k kk，则该值即为最大可获得价值。该方法无需复杂动态规划，仅通过枚举验证即可求解，时间复杂度极低，完美适配题目数据规模约束。

总结

核心逻辑：利用按位与只减不增的特性，从高到低枚举价值，验证是否存在合法物品子集满足体积限制。
关键操作：逆序枚举价值、筛选匹配物品、计算体积按位与、判断合法性。
效率保障：贪心枚举替代状态转移，极简高效地找到最大价值。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;constll mod=998244353;intmain(){ll n,m;cin>>n>>m;vector<ll>v(n+1),w(n+1);for(ll i=1;i<=n;i++)cin>>v[i]>>w[i];for(ll i=2e3;i>=0;i--){ll res=(1<<20ll)-1;for(ll j=1;j<=n;j++){if((w[j]&i)==i)res=res&v[j];}if(res<=m){cout<<i<<endl;return0;}}cout<<0<<endl;return0;}