1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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);
}
}
|
