小苯的01背包easy时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述注此版本为本题的easy简单版与hard困难版唯一的不同之处只有数据范围。小苯有一个容量为k kk的背包现在有n nn个物品每个物品有一个体积v vv和价值w ww他想知道在体积不超过k kk的前提下他最多能装价值为多少的物品。本问题中物品的总体积定义为所装物品的体积的 \按位与总价值也定义为所装物品的价值的 \按位与。如果不选物品则价值为0 00所占体积也为0 00。输入描述输入包含n 1 n1n1行。第一行两个正整数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 \ 91791。价值为3 6 2 3 \ 62362。可以证明不存在比2 22更大的价值。示例2输入3 2 7 3 10 7 9 6输出3说明选择第一个和第二个物品。解题思路本题核心是按位贪心枚举按位与性质验证解决特殊规则的背包问题。利用按位与运算的单调性选取的物品越多价值与体积的按位与结果只会不变或变小因此采用从大到小枚举目标价值的策略。对于每个枚举的价值筛选出所有价值按位与能保留该值的物品计算这些物品体积的按位与结果若结果≤ ≤≤背包容量k kk则该值即为最大可获得价值。该方法无需复杂动态规划仅通过枚举验证即可求解时间复杂度极低完美适配题目数据规模约束。总结核心逻辑利用按位与只减不增的特性从高到低枚举价值验证是否存在合法物品子集满足体积限制。关键操作逆序枚举价值、筛选匹配物品、计算体积按位与、判断合法性。效率保障贪心枚举替代状态转移极简高效地找到最大价值。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M1e610;constll mod998244353;intmain(){ll n,m;cinnm;vectorllv(n1),w(n1);for(ll i1;in;i)cinv[i]w[i];for(ll i2e3;i0;i--){ll res(120ll)-1;for(ll j1;jn;j){if((w[j]i)i)resresv[j];}if(resm){coutiendl;return0;}}cout0endl;return0;}