Struct ZeroOneKnapsackProblemBranchAndBound

Source

pub struct ZeroOneKnapsackProblemBranchAndBound {
    items: Vec<Item>,
    gap: Item,
}

Fields§

§items: Vec<Item>§gap: Item

Implementations§

Source §

impl ZeroOneKnapsackProblemBranchAndBound

Source

pub fn new(iter: I) -> Self
where I: IntoIterator<Item = (i64, i64)>,

Examples found in repository ?

crates/aizu_online_judge/src/dpl/dpl_1_i.rs (line 20)

6pub fn dpl_1_i(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, w: i64, vwm: [(i64, i64, i64)]);
10    let mut item = vec![];
11    for (v, w, mut m) in vwm.take(n) {
12        let mut b = 1;
13        while m > 0 {
14            let k = b.min(m);
15            m -= k;
16            item.push((v * k, w * k));
17            b *= 2;
18        }
19    }
20    let knapsack = ZeroOneKnapsackProblemBranchAndBound::new(item);
21    writeln!(writer, "{}", knapsack.solve(w)).ok();
22}

Source

fn solve_relax(&self, i: usize, max_weight: i64) -> Result<i64, f64>

Examples found in repository ?

crates/competitive/src/combinatorial_optimization/knapsack_problem.rs (line 349)

344    fn dfs(&self, i: usize, cur: Item, max_weight: i64, max_value: &mut i64) -> i64 {
345        if i == self.items.len() {
346            *max_value = cur.value.max(*max_value);
347            return cur.value;
348        }
349        match self.solve_relax(i, max_weight - cur.weight) {
350            Ok(relax) => {
351                *max_value = (relax + cur.value).max(*max_value);
352                return relax + cur.value;
353            }
354            Err(relax) => {
355                if *max_value as f64 > (relax + cur.value as f64) {
356                    return 0;
357                }
358            }
359        }
360        let mut ans = 0i64;
361        if cur.weight + self.items[i].weight <= max_weight {
362            ans = ans.max(self.dfs(i + 1, cur + self.items[i], max_weight, max_value));
363        }
364        ans.max(self.dfs(i + 1, cur, max_weight, max_value))
365    }

Source

fn dfs(&self, i: usize, cur: Item, max_weight: i64, max_value: &mut i64) -> i64

Examples found in repository ?

crates/competitive/src/combinatorial_optimization/knapsack_problem.rs (line 362)

344    fn dfs(&self, i: usize, cur: Item, max_weight: i64, max_value: &mut i64) -> i64 {
345        if i == self.items.len() {
346            *max_value = cur.value.max(*max_value);
347            return cur.value;
348        }
349        match self.solve_relax(i, max_weight - cur.weight) {
350            Ok(relax) => {
351                *max_value = (relax + cur.value).max(*max_value);
352                return relax + cur.value;
353            }
354            Err(relax) => {
355                if *max_value as f64 > (relax + cur.value as f64) {
356                    return 0;
357                }
358            }
359        }
360        let mut ans = 0i64;
361        if cur.weight + self.items[i].weight <= max_weight {
362            ans = ans.max(self.dfs(i + 1, cur + self.items[i], max_weight, max_value));
363        }
364        ans.max(self.dfs(i + 1, cur, max_weight, max_value))
365    }
366    pub fn solve(&self, max_weight: i64) -> i64 {
367        self.dfs(
368            0,
369            Default::default(),
370            max_weight - self.gap.weight,
371            &mut 0i64,
372        ) + self.gap.value
373    }

Source

pub fn solve(&self, max_weight: i64) -> i64

Examples found in repository ?

crates/aizu_online_judge/src/dpl/dpl_1_i.rs (line 21)

6pub fn dpl_1_i(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, w: i64, vwm: [(i64, i64, i64)]);
10    let mut item = vec![];
11    for (v, w, mut m) in vwm.take(n) {
12        let mut b = 1;
13        while m > 0 {
14            let k = b.min(m);
15            m -= k;
16            item.push((v * k, w * k));
17            b *= 2;
18        }
19    }
20    let knapsack = ZeroOneKnapsackProblemBranchAndBound::new(item);
21    writeln!(writer, "{}", knapsack.solve(w)).ok();
22}