2022-07-23: given n items, each item has weight (w[i]) and value (v[i]), only two items can be selected at most, and the weight does not exceed bag. What is the maximum return value? N ＜= 10^5, w[i] ＜

2022-07-23： Given N Item , Each item has a weight (w[i])、 valuable (v[i]),
Only two items can be selected at most , The weight does not exceed bag, What is the maximum return value ？
N <= 10^5, w[i] <= 10^5, v[i] <= 10^5, bag <= 10^5.
The key point of this question ： What data range is very large , Only you need to choose at most two items , This can be used .
From byte ,5.6 written examination .

answer 2022-07-23：

Sort by weight .RMQ.

The code to use rust To write . The code is as follows ：、

use rand::Rng;
fn main() {
    
    let nn: i32 = 12;
    let vv = 20;
    let test_time: i32 = 5000;
    println!(" Beginning of the test ");
    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!(" Something went wrong !");
            break;
        }
    }
    println!(" End of test ");
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    
    if a > b {
    
        a
    } else {
    
        b
    }
}

//  Violence method 
//  Methods written for verification 
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);
}

//  Formal approach 
//  Time complexity 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);
    //  Weight from light to heavy , Label them in turn 1、2、3、4....
    //  Values are built into RMQ structure 
    // 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 {
    
        //  Now comes 0 Cargo No ,RMQ structure 1 Number 
        //  Now comes i Cargo No ,RMQ structure i+1 Number 
        //  Query the boundary of weight , weight   The border  <= bag -  The weight of the current cargo 
        //  In the cargo array , find  <=  The border , Rightmost position i
        // RMQ, Location  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, Current goods , stay RMQ Subscript in 
        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;
    }
}

//  In order to test 
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;
}

The results are as follows ：

---

Zuo Shen java Code