哪个网站可以做英文兼职,莱州哪里有做网站的,网站开发前期功能策划,广州建网站白云区题目描述
注#xff1a;此版本为本题的hard#xff08;困难版#xff09;#xff0c;与easy#xff08;简单版#xff09;唯一的不同之处只有数据范围。
小苯有一个容量为 k 的背包#xff0c;现在有 n 个物品#xff0c;每个物品有一个体积 v 和价值 w#xff0…题目描述
注此版本为本题的hard困难版与easy简单版唯一的不同之处只有数据范围。
小苯有一个容量为 k 的背包现在有 n 个物品每个物品有一个体积 v 和价值 w他想知道在体积不超过 k 的前提下他最多能装价值为多少的物品。
本问题中物品的总体积定义为所装物品的体积的 按位与总价值也定义为所装物品的价值的 按位与。
如果不选物品则价值为 0所占体积也为 0。
输入描述:
输入包含 n1 行。
第一行两个正整数 n,k (1≤n≤2×105,0≤k≤109)分别表示物品个数和背包容量。
加下来 n 行每行两个正整数 vi,wi (0≤vi,wi≤109)表示每个物品的体积和价值。
输出描述:
输出包含一行一个整数表示能装的最大价值。
示例1
输入
复制
3 1
7 3
10 7
9 6
输出
复制
2
说明
选择第一个和第三个物品。
体积为7 917 91。
价值为3 623 62。可以证明不存在比 22 更大的价值。
示例2
输入
复制
3 2
7 3
10 7
9 6
输出
复制
3
说明
选第一个和第二个物品。
思路 由于体积和价值选的越多越小一般背包思路不行
本题采用运算反向思路求最多价值即每一位尽量为1
代码
#includebits/stdc.h
using namespace std;
int main(){int n,k;cinnk;int v[n1],w[n1];int ans0;for(int i1;in;i)cinv[i]w[i];for(int i30;i0;i--){//从高位开始枚举确保价值最高int num(1L30)-1;//初始化最大体积由于运算选的越多体积越小int gans|(1i);//将第i位变1继承其他位置for(int j1;jn;j){if((gw[j])g)numnumv[j];//第i位是1就选}if(numk){//体积不超过kansg;//ans肯定是越来越大的,每次满足第i为变1}}coutansendl;
}
