problemreductions/models/misc/
subset_sum.rs

1//! Subset Sum problem implementation.
2//!
3//! Given a set of integers and a target value, the problem asks whether any
4//! subset sums to exactly the target. One of Karp's original 21 NP-complete
5//! problems (1972).
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::{Problem, SatisfactionProblem};
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "SubsetSum",
14        module_path: module_path!(),
15        description: "Find a subset of integers that sums to exactly a target value",
16        fields: &[
17            FieldInfo { name: "sizes", type_name: "Vec<i64>", description: "Integer sizes s(a) for each element" },
18            FieldInfo { name: "target", type_name: "i64", description: "Target sum B" },
19        ],
20    }
21}
22
23/// The Subset Sum problem.
24///
25/// Given a set of `n` integers and a target `B`, determine whether there exists
26/// a subset whose elements sum to exactly `B`.
27///
28/// # Representation
29///
30/// Each element has a binary variable: `x_i = 1` if element `i` is selected,
31/// `0` otherwise. The problem is satisfiable iff `∑_{i: x_i=1} sizes[i] == target`.
32///
33/// # Example
34///
35/// ```
36/// use problemreductions::models::misc::SubsetSum;
37/// use problemreductions::{Problem, Solver, BruteForce};
38///
39/// let problem = SubsetSum::new(vec![3, 7, 1, 8, 2, 4], 11);
40/// let solver = BruteForce::new();
41/// let solution = solver.find_satisfying(&problem);
42/// assert!(solution.is_some());
43/// ```
44#[derive(Debug, Clone, Serialize, Deserialize)]
45pub struct SubsetSum {
46    sizes: Vec<i64>,
47    target: i64,
48}
49
50impl SubsetSum {
51    /// Create a new SubsetSum instance.
52    pub fn new(sizes: Vec<i64>, target: i64) -> Self {
53        Self { sizes, target }
54    }
55
56    /// Returns the element sizes.
57    pub fn sizes(&self) -> &[i64] {
58        &self.sizes
59    }
60
61    /// Returns the target sum.
62    pub fn target(&self) -> i64 {
63        self.target
64    }
65
66    /// Returns the number of elements.
67    pub fn num_elements(&self) -> usize {
68        self.sizes.len()
69    }
70}
71
72impl Problem for SubsetSum {
73    const NAME: &'static str = "SubsetSum";
74    type Metric = bool;
75
76    fn variant() -> Vec<(&'static str, &'static str)> {
77        crate::variant_params![]
78    }
79
80    fn dims(&self) -> Vec<usize> {
81        vec![2; self.num_elements()]
82    }
83
84    fn evaluate(&self, config: &[usize]) -> bool {
85        if config.len() != self.num_elements() {
86            return false;
87        }
88        if config.iter().any(|&v| v >= 2) {
89            return false;
90        }
91        let total: i64 = config
92            .iter()
93            .enumerate()
94            .filter(|(_, &x)| x == 1)
95            .map(|(i, _)| self.sizes[i])
96            .sum();
97        total == self.target
98    }
99}
100
101impl SatisfactionProblem for SubsetSum {}
102
103crate::declare_variants! {
104    SubsetSum => "2^(num_elements / 2)",
105}
106
107#[cfg(test)]
108#[path = "../../unit_tests/models/misc/subset_sum.rs"]
109mod tests;
problemreductions/models/misc/subset_sum.rs

problemreductions/models/misc/
subset_sum.rs
