1 files changed, 108 insertions, 0 deletions
diff --git a/rust_backend/src/route.rs b/rust_backend/src/route.rs
new file mode 100644
index 0000000..a2c477e
--- /dev/null
+++ b/rust_backend/src/route.rs
@@ -0,0 +1,108 @@
+use std::collections::HashMap;
+
+struct Item {
+    profit: f32,
+    cost: f32,
+    cargo: f32,
+    quantity: usize,
+}
+
+#[derive(PartialEq, Eq, Hash, Clone)]
+struct DiscreteState {
+    cost: isize,
+    cargo: isize,
+}
+
+type StateMap = HashMap<DiscreteState, (f32, Vec<(usize, usize)>)>;
+
+fn discretize(value: f32, precision: f32) -> isize {
+    (value / precision).round() as isize
+}
+
+fn knapsack(items: &[Item], max_cost: f32, max_cargo: f32) -> (f32, Vec<(usize, usize)>) {
+    let mut best_state: StateMap = HashMap::new();
+    let precision = 0.01; // Define the precision level for discretization
+    best_state.insert(DiscreteState { cost: 0, cargo: 0 }, (0.0, vec![]));
+
+    for (index, item) in items.iter().enumerate() {
+        let mut new_state = best_state.clone();
+
+        for (&DiscreteState { cost: current_cost, cargo: current_cargo }, &(current_profit, ref indices)) in &best_state {
+            let max_quantity_cost = ((max_cost - current_cost as f32 * precision) / item.cost).floor() as usize;
+            let max_quantity_cargo = ((max_cargo - current_cargo as f32 * precision) / item.cargo).floor() as usize;
+
+            let quantity = *[
+                item.quantity,
+                max_quantity_cost,
+                max_quantity_cargo,
+            ]
+            .iter()
+            .min()
+            .unwrap();
+
+            if quantity == 0 {
+                continue;
+            }
+
+            let total_cost = discretize(current_cost as f32 * precision + item.cost * (quantity as f32), precision);
+            let total_cargo = discretize(current_cargo as f32 * precision + item.cargo * (quantity as f32), precision);
+            let total_profit = current_profit + item.profit * (quantity as f32);
+
+            let mut new_indices = indices.clone();
+            new_indices.push((index, quantity));
+
+            new_state
+                .entry(DiscreteState { cost: total_cost, cargo: total_cargo })
+                .and_modify(|(existing_profit, existing_indices)| {
+                    if *existing_profit < total_profit {
+                        *existing_profit = total_profit;
+                        *existing_indices = new_indices.clone();
+                    }
+                })
+                .or_insert((total_profit, new_indices));
+        }
+
+        best_state = new_state;
+    }
+
+    best_state.values().max_by(|&(p1, _), &(p2, _)| p1.partial_cmp(&p2).unwrap()).unwrap_or(&(0.0, vec![])).clone()
+}
+
+fn main() {
+    // Example usage with some items defined
+    let items = vec![
+        Item {
+            profit: 60.0,
+            cost: 0.1,
+            cargo: 0.2,
+            quantity: 100,
+        },
+        Item {
+            profit: 100.0,
+            cost: 0.2,
+            cargo: 0.5,
+            quantity: 50,
+        },
+        Item {
+            profit: 100.0,
+            cost: 0.1,
+            cargo: 0.5,
+            quantity: 50,
+        },
+        Item {
+            profit: 100.0,
+            cost: 0.2,
+            cargo: 0.3,
+            quantity: 50,
+        },
+    ];
+
+    let max_cost = 50.0;
+    let max_cargo = 50.0;
+
+    let (max_profit, item_selections) = knapsack(&items, max_cost, max_cargo);
+    println!("Maximum profit: {}", max_profit);
+    for (index, quantity) in item_selections {
+        println!("Item {} taken with quantity: {}", index, quantity);
+    }
+}