2022-07-23：给定N件物品，每个物品有重量(w[i])、有价值(v[i])， 只能最多选两件商品

2022-07-23：给定N件物品，每个物品有重量(w[i])、有价值(v[i])， 只能最多选两件商品，重量不超过bag，返回价值最大能是多少？ N <= 10^5, w[i] <= 10^5, v[i] <= 10^5, bag <= 10^5。 本题的关键点：什么数据范围都很大，唯独只需要最多选两件商品，这个可以利用一下。 来自字节，5.6笔试。

答案2022-07-23：

根据重量排序。RMQ。

代码用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代码