problemreductions/models/misc/
knapsack.rs

1//! Knapsack problem implementation.
2//!
3//! The 0-1 Knapsack problem asks for a subset of items that maximizes
4//! total value while respecting a weight capacity constraint.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::{OptimizationProblem, Problem};
8use crate::types::{Direction, SolutionSize};
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "Knapsack",
14        module_path: module_path!(),
15        description: "Select items to maximize total value subject to weight capacity constraint",
16        fields: &[
17            FieldInfo { name: "weights", type_name: "Vec<i64>", description: "Item weights w_i" },
18            FieldInfo { name: "values", type_name: "Vec<i64>", description: "Item values v_i" },
19            FieldInfo { name: "capacity", type_name: "i64", description: "Knapsack capacity C" },
20        ],
21    }
22}
23
24/// The 0-1 Knapsack problem.
25///
26/// Given `n` items, each with weight `w_i` and value `v_i`, and a capacity `C`,
27/// find a subset `S ⊆ {0, ..., n-1}` such that `∑_{i∈S} w_i ≤ C`,
28/// maximizing `∑_{i∈S} v_i`.
29///
30/// # Representation
31///
32/// Each item has a binary variable: `x_i = 1` if item `i` is selected, `0` otherwise.
33///
34/// # Example
35///
36/// ```
37/// use problemreductions::models::misc::Knapsack;
38/// use problemreductions::{Problem, Solver, BruteForce};
39///
40/// let problem = Knapsack::new(vec![2, 3, 4, 5], vec![3, 4, 5, 7], 7);
41/// let solver = BruteForce::new();
42/// let solution = solver.find_best(&problem);
43/// assert!(solution.is_some());
44/// ```
45#[derive(Debug, Clone, Serialize, Deserialize)]
46pub struct Knapsack {
47    weights: Vec<i64>,
48    values: Vec<i64>,
49    capacity: i64,
50}
51
52impl Knapsack {
53    /// Create a new Knapsack instance.
54    ///
55    /// # Panics
56    /// Panics if `weights` and `values` have different lengths.
57    pub fn new(weights: Vec<i64>, values: Vec<i64>, capacity: i64) -> Self {
58        assert_eq!(
59            weights.len(),
60            values.len(),
61            "weights and values must have the same length"
62        );
63        Self {
64            weights,
65            values,
66            capacity,
67        }
68    }
69
70    /// Returns the item weights.
71    pub fn weights(&self) -> &[i64] {
72        &self.weights
73    }
74
75    /// Returns the item values.
76    pub fn values(&self) -> &[i64] {
77        &self.values
78    }
79
80    /// Returns the knapsack capacity.
81    pub fn capacity(&self) -> i64 {
82        self.capacity
83    }
84
85    /// Returns the number of items.
86    pub fn num_items(&self) -> usize {
87        self.weights.len()
88    }
89}
90
91impl Problem for Knapsack {
92    const NAME: &'static str = "Knapsack";
93    type Metric = SolutionSize<i64>;
94
95    fn variant() -> Vec<(&'static str, &'static str)> {
96        crate::variant_params![]
97    }
98
99    fn dims(&self) -> Vec<usize> {
100        vec![2; self.num_items()]
101    }
102
103    fn evaluate(&self, config: &[usize]) -> SolutionSize<i64> {
104        if config.len() != self.num_items() {
105            return SolutionSize::Invalid;
106        }
107        if config.iter().any(|&v| v >= 2) {
108            return SolutionSize::Invalid;
109        }
110        let total_weight: i64 = config
111            .iter()
112            .enumerate()
113            .filter(|(_, &x)| x == 1)
114            .map(|(i, _)| self.weights[i])
115            .sum();
116        if total_weight > self.capacity {
117            return SolutionSize::Invalid;
118        }
119        let total_value: i64 = config
120            .iter()
121            .enumerate()
122            .filter(|(_, &x)| x == 1)
123            .map(|(i, _)| self.values[i])
124            .sum();
125        SolutionSize::Valid(total_value)
126    }
127}
128
129impl OptimizationProblem for Knapsack {
130    type Value = i64;
131
132    fn direction(&self) -> Direction {
133        Direction::Maximize
134    }
135}
136
137crate::declare_variants! {
138    Knapsack => "2^(num_items / 2)",
139}
140
141#[cfg(test)]
142#[path = "../../unit_tests/models/misc/knapsack.rs"]
143mod tests;
problemreductions/models/misc/knapsack.rs

problemreductions/models/misc/
knapsack.rs
