Hi. I'm trying to write the code for the fractional knapsack algorithm and I need some help figuring out how to sort this vector I created (if it is possible at all). Perhaps my implementation is not the most efficient one, but first let me explain the reasoning behind it.
I'm doing this as a part of a Coursera course. The inputs for the assignment come as stdin from the user. So the first line of input tells the number of N items that you can choose from and the total capacity of your bag.
The next N lines will have the value and the weight of each item.
Here is what I've done so far.
use std::io;
use std::str::FromStr;
fn read_value<T: FromStr>() -> Result<T, <T as FromStr>::Err> {
let mut s = String::new();
io::stdin().read_line(&mut s).expect("could not read from stdin");
s.trim().parse()
}
fn read_values<T: FromStr>() -> Result<Vec<T>, T::Err> {
let mut s = String::new();
io::stdin().read_line(&mut s).expect("could not read from stdin");
s.trim().split_whitespace().map(|word| word.parse()).collect()
}
fn main() {
let capacity = read_values::<f64>().unwrap();
println!("{:?}", capacity);
let length = capacity[0].clone();
let mut items:Vec<Vec<f64>> = Vec::with_capacity(length as usize);
for (_, j) in (0..items.capacity()).enumerate() {
let mut values = read_values::<f64>().unwrap();
let weight = values[0]/values[1];
values.push(weight);
items.push(values);
};
items.sort_by(|a, b| a[2].partial_cmp(b[2]));
println!("{:?}", items);
// items.
let mut vecofvalbyw: Vec<f64> = Vec::with_capacity(items.capacity());
for item in &items {
vecofvalbyw.push(item[0]/item[1]);
}
let mut result = 0f64;
let mut tweight = 0f64;
loop {
// Here items[2][1] is the item with the higher value/weight ratio
if items[2][1] < capacity[1] && items[2][1] < capacity[1]-tweight {
result += &items[2][0];
tweight += &items[2][1];
if tweight == capacity[1] {
break;
}
// Haven't finished the algorithm. Still thinking
}
}
println!("{}", result);
}
As you can see, I haven't finished the algorithm yet because I still haven't figured out what the next move should be. I'm thinking that the next step is to check if the weight of the item exceeds the capacity and add just the fraction that will fit. Then, I would jump to the second most benefiting item and repeat the process.
Ok, but that is not the main problem here.
As a result of my implementation, the items vector is a Vec<Vec>. And it would make it easier to choose which item to add in the bag if I could sort these vectors based on the third element. The third element is the value/weight ratio.
This would give a Vec<Vec> sorted by the third element of each internal vector.
I tried items.sort_by(|a, b| &a[2].partial_cmp(&b[2])); but rust returns
^^^^^^^^^^^^^^^^^^^^^^expected enum std::cmp::Ordering
, found reference
I didn't really understand the error message, but I'm guessing this is not the way to do this. I mean, this is not the way to sort the vector in the first place. The problem is I don't know what the right way of doing would be.
Any advice?
Thanks
Fabrex