competitive::combinatorial_optimization::knapsack_problem

Struct KnapsackProblemSmallValue

pub struct KnapsackProblemSmallValue {
    pub dp: Vec<i64>,
}

Fields§

§dp: Vec<i64>

Implementations§

Source §

impl KnapsackProblemSmallValue

Source

pub fn new(max_value: usize) -> Self

Examples found in repository ?

crates/aizu_online_judge/src/dpl/dpl_1_f.rs (line 10)

6pub fn dpl_1_f(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, vw: [(usize, i64); n]);
10    let mut knapsack = KnapsackProblemSmallValue::new(vw.iter().map(|&(v, _)| v).sum::<usize>());
11    knapsack.extend01(vw);
12    writeln!(writer, "{}", knapsack.solve(w).unwrap_or_default()).ok();
13}

Source

pub fn insert(&mut self, value: usize, weight: i64)

Examples found in repository ?

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

133    pub fn extend<I>(&mut self, iter: I)
134    where
135        I: IntoIterator<Item = (usize, i64)>,
136    {
137        for (value, weight) in iter.into_iter() {
138            self.insert(value, weight);
139        }
140    }

Source

pub fn extend(&mut self, iter: I)
where I: IntoIterator<Item = (usize, i64)>,

Source

pub fn insert01(&mut self, value: usize, weight: i64)

Examples found in repository ?

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

148    pub fn extend01<I>(&mut self, iter: I)
149    where
150        I: IntoIterator<Item = (usize, i64)>,
151    {
152        for (value, weight) in iter.into_iter() {
153            self.insert01(value, weight);
154        }
155    }

Source

pub fn extend01(&mut self, iter: I)
where I: IntoIterator<Item = (usize, i64)>,

Examples found in repository ?

crates/aizu_online_judge/src/dpl/dpl_1_f.rs (line 11)

6pub fn dpl_1_f(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, vw: [(usize, i64); n]);
10    let mut knapsack = KnapsackProblemSmallValue::new(vw.iter().map(|&(v, _)| v).sum::<usize>());
11    knapsack.extend01(vw);
12    writeln!(writer, "{}", knapsack.solve(w).unwrap_or_default()).ok();
13}

Source

pub fn insert_limitation(&mut self, value: usize, weight: i64, count: usize)

Examples found in repository ?

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

169    pub fn extend_limitation<I>(&mut self, iter: I)
170    where
171        I: IntoIterator<Item = (usize, i64, usize)>,
172    {
173        for (value, weight, count) in iter.into_iter() {
174            self.insert_limitation(value, weight, count);
175        }
176    }

Source

pub fn extend_limitation(&mut self, iter: I)
where I: IntoIterator<Item = (usize, i64, usize)>,

Source

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

Examples found in repository ?

crates/aizu_online_judge/src/dpl/dpl_1_f.rs (line 12)

6pub fn dpl_1_f(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, vw: [(usize, i64); n]);
10    let mut knapsack = KnapsackProblemSmallValue::new(vw.iter().map(|&(v, _)| v).sum::<usize>());
11    knapsack.extend01(vw);
12    writeln!(writer, "{}", knapsack.solve(w).unwrap_or_default()).ok();
13}