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)]
54#[serde(try_from = "SubsetSumData")]
55pub struct SubsetSum {
56    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
57    sizes: Vec<BigUint>,
58    #[serde(with = "super::biguint_serde::decimal_biguint")]
59    target: BigUint,
60}
61
62#[derive(Deserialize)]
63struct SubsetSumData {
64    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
65    sizes: Vec<BigUint>,
66    #[serde(with = "super::biguint_serde::decimal_biguint")]
67    target: BigUint,
68}
69
70impl TryFrom<SubsetSumData> for SubsetSum {
71    type Error = crate::registry::ConstructionError;
72    fn try_from(data: SubsetSumData) -> Result<Self, Self::Error> {
73        if data.sizes.iter().any(BigUint::is_zero) {
74            return Err("all sizes must be positive (> 0)".into());
75        }
76        Ok(Self {
77            sizes: data.sizes,
78            target: data.target,
79        })
80    }
81}
82
83impl SubsetSum {
84    /// Create a new SubsetSum instance.
85    ///
86    /// # Panics
87    ///
88    /// Panics if any size is not positive (must be > 0).
89    pub fn new<S, T>(sizes: Vec<S>, target: T) -> Self
90    where
91        S: ToBigUint,
92        T: ToBigUint,
93    {
94        Self::try_new(sizes, target).unwrap_or_else(|error| panic!("{error}"))
95    }
96
97    fn try_new<S, T>(sizes: Vec<S>, target: T) -> Result<Self, crate::registry::ConstructionError>
98    where
99        S: ToBigUint,
100        T: ToBigUint,
101    {
102        let sizes = sizes
103            .into_iter()
104            .map(|size| size.to_biguint().ok_or("all sizes must be positive (> 0)"))
105            .collect::<Result<Vec<_>, _>>()?;
106        let target = target
107            .to_biguint()
108            .ok_or("SubsetSum target must be nonnegative")?;
109        SubsetSumData { sizes, target }.try_into()
110    }
111
112    /// Create a new SubsetSum instance without validating sizes.
113    ///
114    /// This is intended for reductions that produce SubsetSum instances
115    /// where positivity is guaranteed by construction.
116    pub(crate) fn new_unchecked(sizes: Vec<BigUint>, target: BigUint) -> Self {
117        Self { sizes, target }
118    }
119
120    /// Returns the element sizes.
121    pub fn sizes(&self) -> &[BigUint] {
122        &self.sizes
123    }
124
125    /// Returns the target sum.
126    pub fn target(&self) -> &BigUint {
127        &self.target
128    }
129
130    /// Returns the number of elements.
131    pub fn num_elements(&self) -> usize {
132        self.sizes.len()
133    }
134
135    /// Smallest h >= 1 such that every input size and the target are below 2^h.
136    pub fn max_numeric_magnitude_bits(&self) -> u64 {
137        self.sizes
138            .iter()
139            .chain(std::iter::once(&self.target))
140            .fold(1, |bits, value| bits.max(value.bits()))
141    }
142}
143
144impl Problem for SubsetSum {
145    const NAME: &'static str = "SubsetSum";
146    type Solution = Vec<bool>;
147    type Value = crate::types::Or;
148
149    crate::problem_parameters![
150        ("max_numeric_magnitude_bits", max_numeric_magnitude_bits),
151        ("num_elements", num_elements),
152    ];
153
154    fn variant() -> Vec<(&'static str, &'static str)> {
155        crate::variant_params![]
156    }
157
158    fn evaluate(
159        &self,
160        config: &Self::Solution,
161    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
162        Ok({
163            crate::types::Or({
164                if config.len() != self.num_elements() {
165                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
166                        "subset-selection length does not match the elements".into(),
167                    ));
168                }
169                let mut total = BigUint::zero();
170                for (i, &x) in config.iter().enumerate() {
171                    if x {
172                        total += &self.sizes[i];
173                    }
174                }
175                total == self.target
176            })
177        })
178    }
179}
180
181impl crate::solvers::BruteForceProblem for SubsetSum {
182    fn dimensions(&self) -> Vec<usize> {
183        vec![2; self.num_elements()]
184    }
185}
186
187crate::declare_variants! {
188    default SubsetSum => "2^(num_elements / 2)",
189}
190
191crate::register_brute_force! {
192    SubsetSum decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
193}
194
195#[cfg(feature = "example-db")]
196pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
197    // 6 elements [3,7,1,8,2,4], target 11 → select {3,8}
198    vec![crate::example_db::specs::ModelExampleSpec {
199        id: "subset_sum",
200        instance: Box::new(SubsetSum::new(vec![3u32, 7, 1, 8, 2, 4], 11u32)),
201        optimal_config: serde_json::json!(vec![true, false, false, true, false, false]),
202        optimal_value: serde_json::json!(true),
203    }]
204}
205
206#[cfg(test)]
207#[path = "../../unit_tests/models/misc/subset_sum.rs"]
208mod tests;
problemreductions/models/misc/subset_sum.rs

problemreductions/models/misc/
subset_sum.rs
