棒的切割

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. }