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        module_path: module_path!(),
23        description: "Find a subset of positive integers that sums to exactly a target value",
24        fields: &[
25            FieldInfo { name: "sizes", type_name: "Vec<BigUint>", description: "Positive integer sizes s(a) for each element" },
26            FieldInfo { name: "target", type_name: "BigUint", description: "Target sum B" },
27        ],
28    }
29}
30
31/// The Subset Sum problem.
32///
33/// Given a set of `n` positive integers and a target `B`, determine whether
34/// there exists a subset whose elements sum to exactly `B`.
35///
36/// # Representation
37///
38/// Each element has a binary variable: `x_i = 1` if element `i` is selected,
39/// `0` otherwise. The problem is satisfiable iff `∑_{i: x_i=1} sizes[i] == target`.
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::misc::SubsetSum;
45/// use problemreductions::{Problem, Solver, BruteForce};
46///
47/// let problem = SubsetSum::new(vec![3u32, 7, 1, 8, 2, 4], 11u32);
48/// let solver = BruteForce::new();
49/// let solution = solver.find_witness(&problem);
50/// assert!(solution.is_some());
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct SubsetSum {
54    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
55    sizes: Vec<BigUint>,
56    #[serde(with = "super::biguint_serde::decimal_biguint")]
57    target: BigUint,
58}
59
60impl SubsetSum {
61    /// Create a new SubsetSum instance.
62    ///
63    /// # Panics
64    ///
65    /// Panics if any size is not positive (must be > 0).
66    pub fn new<S, T>(sizes: Vec<S>, target: T) -> Self
67    where
68        S: ToBigUint,
69        T: ToBigUint,
70    {
71        let sizes: Vec<BigUint> = sizes
72            .into_iter()
73            .map(|s| s.to_biguint().expect("All sizes must be positive (> 0)"))
74            .collect();
75        assert!(
76            sizes.iter().all(|s| !s.is_zero()),
77            "All sizes must be positive (> 0)"
78        );
79        let target = target
80            .to_biguint()
81            .expect("SubsetSum target must be nonnegative");
82        Self { sizes, target }
83    }
84
85    /// Create a new SubsetSum instance without validating sizes.
86    ///
87    /// This is intended for reductions that produce SubsetSum instances
88    /// where positivity is guaranteed by construction.
89    pub(crate) fn new_unchecked(sizes: Vec<BigUint>, target: BigUint) -> Self {
90        Self { sizes, target }
91    }
92
93    /// Returns the element sizes.
94    pub fn sizes(&self) -> &[BigUint] {
95        &self.sizes
96    }
97
98    /// Returns the target sum.
99    pub fn target(&self) -> &BigUint {
100        &self.target
101    }
102
103    /// Returns the number of elements.
104    pub fn num_elements(&self) -> usize {
105        self.sizes.len()
106    }
107}
108
109impl Problem for SubsetSum {
110    const NAME: &'static str = "SubsetSum";
111    type Value = crate::types::Or;
112
113    fn variant() -> Vec<(&'static str, &'static str)> {
114        crate::variant_params![]
115    }
116
117    fn dims(&self) -> Vec<usize> {
118        vec![2; self.num_elements()]
119    }
120
121    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
122        crate::types::Or({
123            if config.len() != self.num_elements() {
124                return crate::types::Or(false);
125            }
126            if config.iter().any(|&v| v >= 2) {
127                return crate::types::Or(false);
128            }
129            let mut total = BigUint::zero();
130            for (i, &x) in config.iter().enumerate() {
131                if x == 1 {
132                    total += &self.sizes[i];
133                }
134            }
135            total == self.target
136        })
137    }
138}
139
140crate::declare_variants! {
141    default SubsetSum => "2^(num_elements / 2)",
142}
143
144#[cfg(feature = "example-db")]
145pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
146    // 6 elements [3,7,1,8,2,4], target 11 → select {3,8}
147    vec![crate::example_db::specs::ModelExampleSpec {
148        id: "subset_sum",
149        instance: Box::new(SubsetSum::new(vec![3u32, 7, 1, 8, 2, 4], 11u32)),
150        optimal_config: vec![1, 0, 0, 1, 0, 0],
151        optimal_value: serde_json::json!(true),
152    }]
153}
154
155#[cfg(test)]
156#[path = "../../unit_tests/models/misc/subset_sum.rs"]
157mod tests;
problemreductions/models/misc/subset_sum.rs

problemreductions/models/misc/
subset_sum.rs
