haar_lib/algo/knapsack/
small_quantity.rs

1//! 要素数が小さいナップサック問題
2use crate::{algo::merge::inplace_merge, chmax, num::one_zero::Zero};
3use std::ops::Add;
4
5/// 要素数が小さいナップサック問題
6///
7/// **Time complexity** $O(n 2 ^ {n / 2})$
8///
9/// **Space complexity** $O(2 ^ {n / 2})$
10pub fn knapsack_small_quantity<W, V>(cap: W, ws: &[W], vs: &[V]) -> V
11where
12    W: Copy + Add<Output = W> + Ord + Zero,
13    V: Copy + Add<Output = V> + Ord + Zero,
14{
15    let n = ws.len();
16    assert_eq!(ws.len(), vs.len());
17
18    let p = n / 2;
19
20    let zero_w = W::zero();
21    let zero_v = V::zero();
22
23    let mut a: Vec<(W, V)> = vec![(zero_w, zero_v)];
24    let mut b: Vec<(W, V)> = vec![(zero_w, zero_v)];
25
26    for i in 0..p {
27        let k = a.len();
28
29        let temp = a
30            .iter()
31            .map(|&(w, v)| (w + ws[i], v + vs[i]))
32            .collect::<Vec<_>>();
33        a.extend_from_slice(&temp);
34        inplace_merge(&mut a, k);
35    }
36
37    for i in p..n {
38        let k = b.len();
39
40        let temp = b
41            .iter()
42            .map(|&(w, v)| (w + ws[i], v + vs[i]))
43            .collect::<Vec<_>>();
44        b.extend_from_slice(&temp);
45        inplace_merge(&mut b, k);
46    }
47
48    for i in 1..a.len() {
49        chmax!(a[i].1, a[i - 1].1);
50    }
51
52    for i in 1..b.len() {
53        chmax!(b[i].1, b[i - 1].1);
54    }
55
56    b.reverse();
57
58    let mut ret = zero_v;
59    let mut j = 0;
60
61    for (w, v) in a {
62        while j < b.len() && w + b[j].0 > cap {
63            j += 1;
64        }
65        if j >= b.len() {
66            break;
67        }
68        chmax!(ret, v + b[j].1);
69    }
70
71    ret
72}
haar_lib/algo/knapsack/small_quantity.rs

haar_lib/algo/knapsack/
small_quantity.rs
