题目分类:贪心,位运算
思路:看到题目范围(2e5,1e9),首先排除DP
我们需要选择物品子集,使得体积的按位与不超过k,价值的按位与最大。
看到按位与,可以想到应该要在数的二进制方面解出此题
按位与操作具有性质:选择的物品越多,结果的位数可能越少。
考虑二进制按位枚举,如何枚举最优?肯定是从高位到低位枚举
我们可以尝试从最高位到最低位逐位检查是否可以将该位设为1。对于每个候选值,检查是否存在物品子集,其中所有物品的价值包含该候选值,且这些物品的体积按位与结果不超过k。
若满足上述条件,则保留该位为1,同时更新答案;否则,继续检查下一位。
时间复杂度:O(31*n),可行
核心代码如下:(含注释)
int v[N],w[N]; void InfiniteLight() { int n,k; read(n); read(k); Forl(i,1,n){ read(v[i]); //体积 read(w[i]); //价值 } int ans=0; Forr(i,30,0){ //按位从高到低枚举 int tmp=ans|(1LL<<i); //现在正在尝试,看是否能够得到的值,需要保留之前的价值最大值,不然得到的结果一定比之前的最大值小 int vm=-1; //选中的所有价值所占的体积 Forl(j,1,n){ if((tmp & w[j])==tmp){ //满足条件,被选中,更新当前总体积 if(vm==-1){ vm=v[j]; }else{ vm=vm&v[j]; } } } if(vm!=-1 && vm<=k){ //体积<k且需要至少一个物品被选中 ans=tmp; //更新最大值 } } println(ans); return ; }