problemreductions/rules/
partition_knapsack.rs

1//! Reduction from Partition to Knapsack.
2
3use crate::models::misc::{Knapsack, Partition};
4use crate::reduction;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6
7/// Result of reducing Partition to Knapsack.
8#[derive(Debug, Clone)]
9pub struct ReductionPartitionToKnapsack {
10    target: Knapsack,
11}
12
13impl ReductionResult for ReductionPartitionToKnapsack {
14    type Source = Partition;
15    type Target = Knapsack;
16
17    fn target_problem(&self) -> &Self::Target {
18        &self.target
19    }
20
21    fn extract_solution(
22        &self,
23        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
24    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
25        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
26
27        Ok(target_solution.to_vec())
28    }
29}
30
31#[reduction(
32    transform = exact { num_items = "num_elements" },
33    unavailable = {
34        capacity = "the exact target parameter is not represented by this reduction's symbolic transform",
35    }
36)]
37impl ReduceTo<Knapsack> for Partition {
38    type Result = ReductionPartitionToKnapsack;
39
40    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
41        let weights = self.sizes().to_vec();
42        let values = weights.clone();
43        let capacity = self.total_sum() / 2;
44
45        Ok(ReductionPartitionToKnapsack {
46            target: Knapsack::new(weights, values, capacity),
47        })
48    }
49}
50
51#[cfg(feature = "example-db")]
52pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
53    use crate::export::SolutionPair;
54
55    vec![crate::example_db::specs::RuleExampleSpec {
56        id: "partition_to_knapsack",
57        build: || {
58            crate::example_db::specs::rule_example_with_witness::<_, Knapsack>(
59                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
60                SolutionPair {
61                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
62                    target_config: serde_json::json!(vec![true, false, false, true, false, false]),
63                },
64            )
65        },
66    }]
67}
68
69#[cfg(test)]
70#[path = "../unit_tests/rules/partition_knapsack.rs"]
71mod tests;
problemreductions/rules/partition_knapsack.rs

problemreductions/rules/
partition_knapsack.rs
