haar_lib/algo/knapsack/
mod.rs

1//! ナップサック問題
2//!
3//! | function | time complexity | space complexity |
4//! | ---- | ---- | ---- |
5//! | knapsack_small_weight | $O(n \cdot cap)$ | $O(cap)$ |
6//! | knapsack_small_value | $O(n \sum vs)$ | $O(\sum vs)$ |
7//! | knapsack_small_quantity | $O(n 2^{n / 2})$ | $O(2^{n / 2})$ |
8//! | knapsack_limited | $O(n \cdot cap \log \max ms)$ | $O(cap)$ |
9//! | knapsack_unlimited | $O(n \cdot cap)$ | $O(cap)$ |
10
11pub mod limited;
12pub mod small_quantity;
13pub mod small_value;
14pub mod small_weight;
15pub mod unlimited;
16
17#[cfg(test)]
18mod tests {
19    use super::{limited::*, small_quantity::*, small_value::*, small_weight::*, unlimited::*};
20
21    #[test]
22    fn test() {
23        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_B
24        assert_eq!(knapsack_small_weight(5, &[2, 2, 1, 3], &[4, 5, 2, 8]), 13);
25        assert_eq!(knapsack_small_weight(20, &[9, 10], &[5, 4]), 9);
26
27        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_F
28        assert_eq!(knapsack_small_value(5, &[2, 2, 1, 3], &[4, 5, 2, 8]), 13);
29        assert_eq!(knapsack_small_value(20, &[9, 10], &[5, 4]), 9);
30
31        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_G
32        assert_eq!(
33            knapsack_limited(8, &[3, 1, 2, 2], &[4, 2, 1, 3], &[2, 1, 4, 2]),
34            12
35        );
36        assert_eq!(knapsack_limited(100, &[1, 1], &[1, 2], &[100, 50]), 150);
37
38        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_C
39        assert_eq!(knapsack_unlimited(8, &[2, 2, 1, 3], &[4, 5, 2, 8]), 21);
40        assert_eq!(knapsack_unlimited(20, &[9, 10], &[5, 4]), 10);
41        assert_eq!(knapsack_unlimited(9, &[1, 1, 2], &[2, 3, 5]), 27);
42
43        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_H
44        assert_eq!(knapsack_small_quantity(5, &[2, 2, 1, 3], &[4, 5, 2, 8]), 13);
45        assert_eq!(knapsack_small_quantity(20, &[9, 10], &[5, 4]), 9);
46    }
47}
haar_lib/algo/knapsack/mod.rs

haar_lib/algo/knapsack/
mod.rs
