knapsack/
knapsack.rs

1use branch_and_bound::{Subproblem, SubproblemResolution};
2
3mod knapsack_core;
4use knapsack_core::*;
5
6#[cfg(test)]
7mod knapsack_samples;
8
9impl Subproblem for KnapsackSubproblem {
10    type Score = u64;
11
12    fn branch_or_evaluate(&mut self) -> SubproblemResolution<Self, Self::Score> {
13        if self.capacity_left() == 0 {
14            return SubproblemResolution::Solved(self.collected_val());
15        }
16
17        if self.have_items() {
18            let mut child_include = self.clone();
19            child_include.include_next();
20
21            let dummy = KnapsackSubproblem::new(0, vec![]);
22            let mut child_exclude = std::mem::replace(self, dummy); // Avoid copying: reuse `self`
23            child_exclude.drop_next();
24
25            SubproblemResolution::Branched(Box::new([child_include, child_exclude].into_iter()))
26        } else {
27            SubproblemResolution::Solved(self.collected_val())
28        }
29    }
30
31    fn bound(&self) -> Self::Score {
32        self.bound()
33    }
34}
35
36fn solve(problem: KnapsackSubproblem) -> Option<KnapsackSubproblem> {
37    branch_and_bound::solve(problem, branch_and_bound::TraverseMethod::BreadthFirst)
38}
39
40fn main() {
41    examples_main();
42}
knapsack/knapsack.rs

knapsack/
knapsack.rs
