algorithms_edu/problems/dp/
knapsack.rs

1//! This mod contains a dynamic programming solutions to the classic 0/1 knapsack problem where are
2//! you are trying to maximize the total profit of items selected without exceeding the capacity of
3//! your knapsack.
4//!
5//! Time Complexity: O(nW) Space Complexity: O(nW)
6//!
7//! # Resources
8//!
9//! - [W. Fiset's video](https://www.youtube.com/watch?v=cJ21moQpofY)
10
11use std::cmp::max;
12
13pub struct Item {
14    value: usize,
15    weight: usize,
16}
17
18impl Item {
19    pub fn new(value: usize, weight: usize) -> Self {
20        Self { value, weight }
21    }
22}
23
24pub fn knapsack(capacity: usize, items: &[Item]) -> (usize, Vec<usize>) {
25    let m = items.len();
26    let n = capacity;
27    // Initialize a table where individual rows represent items
28    // and columns represent the weight of the knapsack.
29    let mut dp = vec![vec![0; n + 1]; m + 1];
30    for i in 1..=m {
31        let v = items[i - 1].value;
32        let w = items[i - 1].weight;
33        for j in 0..w {
34            dp[i][j] = dp[i - 1][j];
35        }
36        for j in w..=n {
37            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
38        }
39    }
40
41    let mut selection = Vec::new();
42
43    // Using the information inside the table we can backtrack and determine
44    // which items were selected during the dynamic programming phase. The idea
45    // is that if DP[i][sz] != DP[i-1][sz] then the item was selected
46    let mut sz = n;
47    for i in (1..=m).rev() {
48        if dp[i][sz] != dp[i - 1][sz] {
49            let item_index = i - 1;
50            selection.push(item_index);
51            sz -= items[item_index].weight
52        }
53    }
54
55    (dp[m][n], selection)
56}
57
58pub fn knapsack_value_only(capacity: usize, items: &[Item]) -> usize {
59    let n = capacity;
60    // Initialize a table where individual rows represent items
61    // and columns represent the weight of the knapsack.
62    // To save space, only two rows are stored.
63    let mut prev = vec![0; n + 1];
64    let mut curr;
65    for &Item { value, weight } in items {
66        curr = vec![0; n + 1];
67        curr[..weight].clone_from_slice(&prev[..weight]);
68        for j in weight..=n {
69            curr[j] = max(prev[j], prev[j - weight] + value);
70        }
71        std::mem::swap(&mut prev, &mut curr);
72    }
73    prev[n]
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79    #[test]
80    fn test_knapsack() {
81        let items = vec![
82            Item::new(2, 3),
83            Item::new(2, 1),
84            Item::new(4, 3),
85            Item::new(5, 4),
86            Item::new(3, 2),
87        ];
88        let (max_val, selection) = knapsack(7, &items);
89        assert_eq!(max_val, 10);
90        assert_eq!(&selection, &[4, 3, 1]);
91
92        assert_eq!(knapsack_value_only(7, &items), 10);
93    }
94}
algorithms_edu/problems/dp/knapsack.rs

algorithms_edu/problems/dp/
knapsack.rs
