2022-07-23：给定N件物品，每个物品有重量(w[i])、有价值(v[i])， 只能最多选两件商品，重量不超过bag，返回价值最大能是多少？ N ＜= 10^5, w[i] ＜= 10^5, v

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

2022-07-23：给定N件物品，每个物品有重量(w[i])、有价值(v[i])， 只能最多选两件商品，重量不超过bag，返回价值最大能是多少？ N ＜= 10^5, w[i] ＜= 10^5, v的相关教程结束。