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(&self, target_solution: &[usize]) -> Vec<usize> {
22        target_solution.to_vec()
23    }
24}
25
26fn partition_size_to_i64(value: u64) -> i64 {
27    i64::try_from(value)
28        .expect("Partition -> Knapsack requires all sizes and total_sum / 2 to fit in i64")
29}
30
31#[reduction(overhead = {
32    num_items = "num_elements",
33})]
34impl ReduceTo<Knapsack> for Partition {
35    type Result = ReductionPartitionToKnapsack;
36
37    fn reduce_to(&self) -> Self::Result {
38        let weights: Vec<i64> = self
39            .sizes()
40            .iter()
41            .copied()
42            .map(partition_size_to_i64)
43            .collect();
44        let values = weights.clone();
45        let capacity = partition_size_to_i64(self.total_sum() / 2);
46
47        ReductionPartitionToKnapsack {
48            target: Knapsack::new(weights, values, capacity),
49        }
50    }
51}
52
53#[cfg(feature = "example-db")]
54pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
55    use crate::export::SolutionPair;
56
57    vec![crate::example_db::specs::RuleExampleSpec {
58        id: "partition_to_knapsack",
59        build: || {
60            crate::example_db::specs::rule_example_with_witness::<_, Knapsack>(
61                Partition::new(vec![3, 1, 1, 2, 2, 1]),
62                SolutionPair {
63                    source_config: vec![1, 0, 0, 1, 0, 0],
64                    target_config: vec![1, 0, 0, 1, 0, 0],
65                },
66            )
67        },
68    }]
69}
70
71#[cfg(test)]
72#[path = "../unit_tests/rules/partition_knapsack.rs"]
73mod tests;
problemreductions/rules/partition_knapsack.rs

problemreductions/rules/
partition_knapsack.rs
