problemreductions/models/misc/
subset_sum.rs

1//! Subset Sum problem implementation.
2//!
3//! Given a set of positive integers and a target value, the problem asks whether
4//! any subset sums to exactly the target. One of Karp's original 21 NP-complete
5//! problems (1972).
6//!
7//! This implementation uses arbitrary-precision integers (`BigUint`) so
8//! reductions can construct large instances without fixed-width overflow.
9
10use crate::registry::{FieldInfo, ProblemSchemaEntry};
11use crate::traits::Problem;
12use num_bigint::{BigUint, ToBigUint};
13use num_traits::Zero;
14use serde::{Deserialize, Serialize};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "SubsetSum",
19        display_name: "Subset Sum",
20        aliases: &[],
21        dimensions: &[],
22        category: crate::registry::ProblemCategory::Misc,
23        module_path: module_path!(),
24        description: "Find a subset of positive integers that sums to exactly a target value",
25        fields: &[
26            FieldInfo { name: "sizes", type_name: "Vec<BigUint>", description: "Positive integer sizes s(a) for each element" },
27            FieldInfo { name: "target", type_name: "BigUint", description: "Target sum B" },
28        ],
29    }
30}
31
32/// The Subset Sum problem.
33///
34/// Given a set of `n` positive integers and a target `B`, determine whether
35/// there exists a subset whose elements sum to exactly `B`.
36///
37/// # Representation
38///
39/// Each element has a binary variable: `x_i = 1` if element `i` is selected,
40/// `0` otherwise. The problem is satisfiable iff `∑_{i: x_i=1} sizes[i] == target`.
41///
42/// # Example
43///
44/// ```
45/// use problemreductions::models::misc::SubsetSum;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// let problem = SubsetSum::new(vec![3u32, 7, 1, 8, 2, 4], 11u32);
49/// let solver = BruteForce::new();
50/// let solution = solver.solve(&problem).unwrap();
51/// assert!(solution.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize, Deserialize)]
54pub struct SubsetSum {
55    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
56    sizes: Vec<BigUint>,
57    #[serde(with = "super::biguint_serde::decimal_biguint")]
58    target: BigUint,
59}
60
61impl SubsetSum {
62    /// Create a new SubsetSum instance.
63    ///
64    /// # Panics
65    ///
66    /// Panics if any size is not positive (must be > 0).
67    pub fn new<S, T>(sizes: Vec<S>, target: T) -> Self
68    where
69        S: ToBigUint,
70        T: ToBigUint,
71    {
72        let sizes: Vec<BigUint> = sizes
73            .into_iter()
74            .map(|s| s.to_biguint().expect("All sizes must be positive (> 0)"))
75            .collect();
76        assert!(
77            sizes.iter().all(|s| !s.is_zero()),
78            "All sizes must be positive (> 0)"
79        );
80        let target = target
81            .to_biguint()
82            .expect("SubsetSum target must be nonnegative");
83        Self { sizes, target }
84    }
85
86    /// Create a new SubsetSum instance without validating sizes.
87    ///
88    /// This is intended for reductions that produce SubsetSum instances
89    /// where positivity is guaranteed by construction.
90    pub(crate) fn new_unchecked(sizes: Vec<BigUint>, target: BigUint) -> Self {
91        Self { sizes, target }
92    }
93
94    /// Returns the element sizes.
95    pub fn sizes(&self) -> &[BigUint] {
96        &self.sizes
97    }
98
99    /// Returns the target sum.
100    pub fn target(&self) -> &BigUint {
101        &self.target
102    }
103
104    /// Returns the number of elements.
105    pub fn num_elements(&self) -> usize {
106        self.sizes.len()
107    }
108}
109
110impl Problem for SubsetSum {
111    const NAME: &'static str = "SubsetSum";
112    type Solution = Vec<bool>;
113    type Value = crate::types::Or;
114
115    crate::problem_parameters![("num_elements", num_elements),];
116
117    fn variant() -> Vec<(&'static str, &'static str)> {
118        crate::variant_params![]
119    }
120
121    fn evaluate(
122        &self,
123        config: &Self::Solution,
124    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
125        Ok({
126            crate::types::Or({
127                if config.len() != self.num_elements() {
128                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
129                        "subset-selection length does not match the elements".into(),
130                    ));
131                }
132                let mut total = BigUint::zero();
133                for (i, &x) in config.iter().enumerate() {
134                    if x {
135                        total += &self.sizes[i];
136                    }
137                }
138                total == self.target
139            })
140        })
141    }
142}
143
144impl crate::solvers::BruteForceProblem for SubsetSum {
145    fn dimensions(&self) -> Vec<usize> {
146        vec![2; self.num_elements()]
147    }
148}
149
150crate::declare_variants! {
151    default SubsetSum => "2^(num_elements / 2)",
152}
153
154crate::register_brute_force! {
155    SubsetSum decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
156}
157
158#[cfg(feature = "example-db")]
159pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
160    // 6 elements [3,7,1,8,2,4], target 11 → select {3,8}
161    vec![crate::example_db::specs::ModelExampleSpec {
162        id: "subset_sum",
163        instance: Box::new(SubsetSum::new(vec![3u32, 7, 1, 8, 2, 4], 11u32)),
164        optimal_config: serde_json::json!(vec![true, false, false, true, false, false]),
165        optimal_value: serde_json::json!(true),
166    }]
167}
168
169#[cfg(test)]
170#[path = "../../unit_tests/models/misc/subset_sum.rs"]
171mod tests;
problemreductions/models/misc/subset_sum.rs

problemreductions/models/misc/
subset_sum.rs
