背包问题

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