knapsack/
knapsack.rs

1use branch_and_bound::{Subproblem, SubproblemResolution};
2
3mod knapsack_common;
4use knapsack_common::*;
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        // If I was to add items greadily (items are ordered by ratio) and perfectly fill
33        // the knapsack, that would be the best solution.
34        //
35        // The heuristic is as follows: I try to use a bit more than
36        // the capacity of the knapsack and when that is filled, I claim that
37        // that's the best we could possibly get
38        // (because that's the best we could possibly get with a slightly larger knapsack).
39
40        let mut val = self.collected_val();
41        let mut capacity = self.capacity_left();
42        for item in self.future_items() {
43            if item.weight < capacity {
44                val += item.price;
45                capacity -= item.weight;
46            } else {
47                // Exceeding the capacity with this item
48                return val + item.price;
49            }
50        }
51        val
52    }
53}
54
55fn solve(problem: KnapsackSubproblem) -> Option<KnapsackSubproblem> {
56    branch_and_bound::solve(problem, branch_and_bound::TraverseMethod::BestFirst)
57}
58
59fn main() {
60    let i = |w, p| Item {
61        weight: w,
62        price: p,
63    };
64
65    // Just an arbitrary example I made up
66    let problem = KnapsackSubproblem::new(9, vec![i(6, 5), i(1, 1), i(2, 2), i(4, 4)]);
67
68    if let Some(packed) = solve(problem) {
69        println!("Solved: {:#?}", packed.into_items());
70    } else {
71        println!("No solution!");
72    }
73}
knapsack/knapsack.rs

knapsack/
knapsack.rs
