competitive::combinatorial_optimization::knapsack_problem

Struct ZeroOneKnapsackProblemBranchAndBound

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 18)

5pub fn dpl_1_i(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, w: i64, vwm: [(i64, i64, i64); iter n]);
8    let mut item = vec![];
9    for (v, w, mut m) in vwm {
10        let mut b = 1;
11        while m > 0 {
12            let k = b.min(m);
13            m -= k;
14            item.push((v * k, w * k));
15            b *= 2;
16        }
17    }
18    let knapsack = ZeroOneKnapsackProblemBranchAndBound::new(item);
19    pp!(knapsack.solve(w));
20}

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 19)

5pub fn dpl_1_i(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, w: i64, vwm: [(i64, i64, i64); iter n]);
8    let mut item = vec![];
9    for (v, w, mut m) in vwm {
10        let mut b = 1;
11        while m > 0 {
12            let k = b.min(m);
13            m -= k;
14            item.push((v * k, w * k));
15            b *= 2;
16        }
17    }
18    let knapsack = ZeroOneKnapsackProblemBranchAndBound::new(item);
19    pp!(knapsack.solve(w));
20}