dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

//! special case of dual unbounded knapsack table just.
//! that all weights are 1.

pub fn subset_sum_min_count_table(
    values: &[u64],
    size: usize,
) -> Vec<Option<u64>> {
    let mut at_least = vec![None; size];

    at_least[0] = Some(0);

    for &v in values {
        let v = v as usize;

        for j in (v..size).rev() {
            if at_least[j - v].is_none() {
                continue;
            }

            let c = Some(at_least[j - v].unwrap() + 1);

            if at_least[j].is_none() || c < at_least[j] {
                at_least[j] = c;
            }
        }
    }

    at_least
}

pub fn subset_sum_min_count_table_2(
    values: &[u64],
    size: usize,
) -> Vec<Option<u64>> {
    let mut at_least = vec![None; size];

    at_least[0] = Some(0);

    for i in 0..size {
        if at_least[i].is_none() {
            continue;
        }

        let nw = Some(at_least[i].unwrap() + 1);

        for &v in values {
            let v = v as usize;

            let j = i + v;

            if j >= size {
                continue;
            }

            if at_least[j].is_none() || nw < at_least[j] {
                at_least[j] = nw;
            }
        }
    }

    at_least
}

// TODO
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}