背包问题

1. //! Solves the knapsack problem
2. use std::cmp::max;

4. /// knapsack_table(w, weights, values) returns the knapsack table (`n`, `m`) with maximum values, where `n` is number of items
5. ///
6. /// Arguments:
7. ///     * `w` - knapsack capacity
8. ///     * `weights` - set of weights for each item
9. ///     * `values` - set of values for each item
10. fn knapsack_table(w: &usize, weights: &[usize], values: &[usize]) -> Vec<Vec<usize>> {
11. // Initialize `n` - number of items
12. let n: usize = weights.len();
13. // Initialize `m`
14. // m[i, w] - the maximum value that can be attained with weight less that or equal to `w` using items up to `i`
15. let mut m: Vec<Vec<usize>> = vec![vec![0; w + 1]; n + 1];

17. for i in 0..=n {
18. for j in 0..=*w {
19. // m[i, j] compiled according to the following rule:
20. if i == 0 || j == 0 {
21. m[i][j] = 0;
22. } else if weights[i - 1] <= j {
23. // If `i` is in the knapsack
24. // Then m[i, j] is equal to the maximum value of the knapsack,
25. // where the weight `j` is reduced by the weight of the `i-th` item and the set of admissible items plus the value `k`
26. m[i][j] = max(values[i - 1] + m[i - 1][j - weights[i - 1]], m[i - 1][j]);
27. } else {
28. // If the item `i` did not get into the knapsack
29. // Then m[i, j] is equal to the maximum cost of a knapsack with the same capacity and a set of admissible items
30. m[i][j] = m[i - 1][j]
31. }
32. }
33. }
34. m
35. }

37. /// knapsack_items(weights, m, i, j) returns the indices of the items of the optimal knapsack (from 1 to `n`)
38. ///
39. /// Arguments:
40. ///     * `weights` - set of weights for each item
41. ///     * `m` - knapsack table with maximum values
42. ///     * `i` - include items 1 through `i` in knapsack (for the initial value, use `n`)
43. ///     * `j` - maximum weight of the knapsack
44. fn knapsack_items(weights: &[usize], m: &[Vec<usize>], i: usize, j: usize) -> Vec<usize> {
45. if i == 0 {
46. return vec![];
47. }
48. if m[i][j] > m[i - 1][j] {
49. let mut knap: Vec<usize> = knapsack_items(weights, m, i - 1, j - weights[i - 1]);
50. knap.push(i);
51. knap
52. } else {
53. knapsack_items(weights, m, i - 1, j)
54. }
55. }

57. /// knapsack(w, weights, values) returns the tuple where first value is `optimal profit`,
58. /// second value is `knapsack optimal weight` and the last value is `indices of items`, that we got (from 1 to `n`)
59. ///
60. /// Arguments:
61. ///     * `w` - knapsack capacity
62. ///     * `weights` - set of weights for each item
63. ///     * `values` - set of values for each item
64. ///
65. /// Complexity
66. ///     - time complexity: O(nw),
67. ///     - space complexity: O(nw),
68. ///
69. /// where `n` and `w` are `number of items` and `knapsack capacity`
70. pub fn knapsack(w: usize, weights: Vec<usize>, values: Vec<usize>) -> (usize, usize, Vec<usize>) {
71. // Checks if the number of items in the list of weights is the same as the number of items in the list of values
72. assert_eq!(weights.len(), values.len(), "Number of items in the list of weights doesn't match the number of items in the list of values!");
73. // Initialize `n` - number of items
74. let n: usize = weights.len();
75. // Find the knapsack table
76. let m: Vec<Vec<usize>> = knapsack_table(&w, &weights, &values);
77. // Find the indices of the items
78. let items: Vec<usize> = knapsack_items(&weights, &m, n, w);
79. // Find the total weight of optimal knapsack
80. let mut total_weight: usize = 0;
81. for i in items.iter() {
82. total_weight += weights[i - 1];
83. }
84. // Return result
85. (m[n][w], total_weight, items)
86. }

88. #[cfg(test)]
89. mod tests {
90. // Took test datasets from https://people.sc.fsu.edu/~jburkardt/datasets/bin_packing/bin_packing.html
91. use super::*;

93. #[test]
94. fn test_p02() {
95. assert_eq!(
96. (51, 26, vec![2, 3, 4]),
97. knapsack(26, vec![12, 7, 11, 8, 9], vec![24, 13, 23, 15, 16])
98. );
99. }

101. #[test]
102. fn test_p04() {
103. assert_eq!(
104. (150, 190, vec![1, 2, 5]),
105. knapsack(
106. 190,
107. vec![56, 59, 80, 64, 75, 17],
108. vec![50, 50, 64, 46, 50, 5]
109. )
110. );
111. }

113. #[test]
114. fn test_p01() {
115. assert_eq!(
116. (309, 165, vec![1, 2, 3, 4, 6]),
117. knapsack(
118. 165,
119. vec![23, 31, 29, 44, 53, 38, 63, 85, 89, 82],
120. vec![92, 57, 49, 68, 60, 43, 67, 84, 87, 72]
121. )
122. );
123. }

125. #[test]
126. fn test_p06() {
127. assert_eq!(
128. (1735, 169, vec![2, 4, 7]),
129. knapsack(
130. 170,
131. vec![41, 50, 49, 59, 55, 57, 60],
132. vec![442, 525, 511, 593, 546, 564, 617]
133. )
134. );
135. }

137. #[test]
138. fn test_p07() {
139. assert_eq!(
140. (1458, 749, vec![1, 3, 5, 7, 8, 9, 14, 15]),
141. knapsack(
142. 750,
143. vec![70, 73, 77, 80, 82, 87, 90, 94, 98, 106, 110, 113, 115, 118, 120],
144. vec![135, 139, 149, 150, 156, 163, 173, 184, 192, 201, 210, 214, 221, 229, 240]
145. )
146. );
147. }
148. }