棒的切割

  1. //! Solves the rod-cutting problem
  2. use std::cmp::max;
  4. /// `rod_cut(p)` returns the maximum possible profit if a rod of length `n` = `p.len()`
  5. /// is cut into up to `n` pieces, where the profit gained from each piece of length
  6. /// `l` is determined by `p[l - 1]` and the total profit is the sum of the profit
  7. /// gained from each piece.
  8. ///
  9. /// # Arguments
  10. ///    - `p` - profit for rods of length 1 to n inclusive
  11. ///
  12. /// # Complexity
  13. ///    - time complexity: O(n^2),
  14. ///    - space complexity: O(n^2),
  15. ///
  16. /// where n is the length of `p`.
  17. pub fn rod_cut(p: &[usize]) -> usize {
  18.     let n = p.len();
  19.     // f is the dynamic programming table
  20.     let mut f = vec![0; n];
  22.     for i in 0..n {
  23.         let mut max_price = p[i];
  24.         for j in 1..=i {
  25.             max_price = max(max_price, p[j - 1] + f[i - j]);
  26.         }
  27.         f[i] = max_price;
  28.     }
  30.     // accomodate for input with length zero
  31.     if n != 0 {
  32.         f[n - 1]
  33.     } else {
  34.         0
  35.     }
  36. }
  38. #[cfg(test)]
  39. mod tests {
  40.     use super::rod_cut;
  42.     #[test]
  43.     fn test_rod_cut() {
  44.         assert_eq!(0, rod_cut(&[]));
  45.         assert_eq!(15, rod_cut(&[5, 8, 2]));
  46.         assert_eq!(10, rod_cut(&[1, 5, 8, 9]));
  47.         assert_eq!(25, rod_cut(&[5, 8, 2, 1, 7]));
  48.         assert_eq!(87, rod_cut(&[0, 0, 0, 0, 0, 87]));
  49.         assert_eq!(49, rod_cut(&[7, 6, 5, 4, 3, 2, 1]));
  50.         assert_eq!(22, rod_cut(&[1, 5, 8, 9, 10, 17, 17, 20]));
  51.         assert_eq!(60, rod_cut(&[6, 4, 8, 2, 5, 8, 2, 3, 7, 11]));
  52.         assert_eq!(30, rod_cut(&[1, 5, 8, 9, 10, 17, 17, 20, 24, 30]));
  53.         assert_eq!(12, rod_cut(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]));
  54.     }
  55. }