2022-07-23：给定N件物品，每个物品有重量(wi)、有价值(vi)，
只能最多选两件商品，重量不超过bag，返回价值最大能是多少？
N <= 10^5, wi <= 10^5, vi <= 10^5, bag <= 10^5。
本题的关键点：什么数据范围都很大，唯独只需要最多选两件商品，这个可以利用一下。
来自字节，5.6笔试。
答案2022-07-23：
根据重量排序。RMQ。
代码用rust编写。代码如下：、
代码语言：rust复制use rand::Rng;
fn main() {
let nn: i32 = 12;
let vv = 20;
let test_time: i32 = 5000;
println!("测试开始");
for i in 0..test_time {
let n = rand::thread_rng().gen_range(0, nn) 1;
let mut w = random_array(n, vv);
let mut v = random_array(n, vv);
let bag = rand::thread_rng().gen_range(0, vv * 1);
let ans1 = max1(&mut w, &mut v, bag);
let ans2 = max2(&mut w, &mut v, bag);
if ans1 != ans2 {
println!("i = {}", i);
println!("bag = {}", bag);
println!("w = {:?}", w);
println!("v = {:?}", v);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
println!("出错了!");
break;
}
}
println!("测试结束");
}
fn get_max<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 暴力方法
// 为了验证而写的方法
fn max1(w: &mut Vec<i32>, v: &mut Vec<i32>, bag: i32) -> i32 {
return process1(w, v, 0, 2, bag);
}
fn process1(
w: &mut Vec<i32>,
v: &mut Vec<i32>,
index: i32,
rest_number: i32,
rest_weight: i32,
) -> i32 {
if rest_number < 0 || rest_weight < 0 {
return -1;
}
if index == w.len() as i32 {
return 0;
}
let p1 = process1(w, v, index 1, rest_number, rest_weight);
let mut p2 = -1;
let next = process1(
w,
v,
index 1,
rest_number - 1,
rest_weight - w[index as usize],
);
if next != -1 {
p2 = v[index as usize] next;
}
return get_max(p1, p2);
}
// 正式方法
// 时间复杂度O(N * logN)
fn max2(w: &mut Vec<i32>, v: &mut Vec<i32>, bag: i32) -> i32 {
let n = w.len() as i32;
let mut arr: Vec<Vec<i32>> = vec![];
for i in 0..n {
arr.push(vec![]);
for _ in 0..2 {
arr[i as usize].push(0);
}
}
for i in 0..n {
arr[i as usize][0] = w[i as usize];
arr[i as usize][1] = v[i as usize];
}
// O(N * logN)
arr.sort_by(|a, b| a[0].cmp(&b[0]));
// println!("arr = {:?}", arr);
// 重量从轻到重，依次标号1、2、3、4....
// 价值依次被构建成了RMQ结构
// O(N * logN)
let mut rmq = RMQ::new(&mut arr);
let mut ans = 0;
// N * logN
let mut i = 0;
let mut j = 1;
while i < n && arr[i as usize][0] <= bag {
// 当前来到0号货物，RMQ结构1号
// 当前来到i号货物，RMQ结构i 1号
// 查询重量的边界，重量 边界 <= bag - 当前货物的重量
// 货物数组中，找到 <= 边界，最右的位置i
// RMQ，位置 i 1
let limit = bag - arr[i as usize][0];
let right0 = right(&mut arr, limit) 1;
let mut rest: i32 = 0;
// j == i 1，当前的货物，在RMQ里的下标
if right0 == j {
rest = rmq.fmax(1, right0 - 1);
} else if right0 < j {
rest = rmq.fmax(1, right0);
} else {
// right > j
rest = get_max(rmq.fmax(1, j - 1), rmq.fmax(j 1, right0));
}
// println!("ans = {}", ans);
// println!("arr[i as usize][1] rest = {}", arr[i as usize][1] rest);
ans = get_max(ans, arr[i as usize][1] rest);
// println!("222 ans = {}", ans);
// println!("----------");
i = 1;
j = 1;
}
return ans;
}
fn right(arr: &mut Vec<Vec<i32>>, limit: i32) -> i32 {
let mut l = 0;
let mut r = arr.len() as i32 - 1;
let mut m = 0;
let mut ans = -1;
while l <= r {
m = (l r) / 2;
if arr[m as usize][0] <= limit {
ans = m;
l = m 1;
} else {
r = m - 1;
}
}
return ans;
}
pub struct RMQ {
pub max: Vec<Vec<i32>>,
}
impl RMQ {
pub fn new(arr: &mut Vec<Vec<i32>>) -> Self {
let mut ans: RMQ = RMQ { max: vec![] };
let n = arr.len() as i32;
let k = ans.power2(n);
let mut max: Vec<Vec<i32>> = vec![];
for i in 0..n 1 {
max.push(vec![]);
for _ in 0..k 1 {
max[i as usize].push(0);
}
}
for i in 1..=n {
max[i as usize][0] = arr[(i - 1) as usize][1];
}
let mut j = 1;
while (1 << j) <= n {
let mut i = 1;
while i (1 << j) - 1 <= n {
max[i as usize][j as usize] = get_max(
max[i as usize][(j - 1) as usize],
max[(i (1 << (j - 1))) as usize][(j - 1) as usize],
);
i = 1;
}
j = 1;
}
ans.max = max;
return ans;
}
pub fn fmax(&mut self, l: i32, r: i32) -> i32 {
if r < l {
return 0;
}
let k = self.power2(r - l 1);
return get_max(
self.max[l as usize][k as usize],
self.max[(r - (1 << k) 1) as usize][k as usize],
);
}
fn power2(&mut self, m: i32) -> i32 {
let mut ans = 0;
while (1 << ans) <= (m >> 1) {
ans = 1;
}
return ans;
}
}
// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut ans: Vec<i32> = vec![];
for _ in 0..n {
ans.push(rand::thread_rng().gen_range(0, v));
}
return ans;
}执行结果如下：
在这里插入图片描述左神java代码
