Greedy Knapsack solver

knapsack.rs

use std::fmt::Debug;
use std::str::FromStr;

fn main() {
    let row = read_vector::<u64>();
    let n = row[0] as usize;
    let k = row[1];

    let items = read_items(n);
    let knapsack = Knapsack::new(k, items);

    if let Ok(sack_content) = greedy_by_value_density(&knapsack) {
        print_result(&knapsack, &sack_content);
    }
}

fn print_result(knapsack: &Knapsack, sack_content: &SackContent) {
    println!("{} 0", sack_content.objective);

    for item in knapsack.items().iter() {
        let is_selected = if sack_content.contains(item) { 1 } else { 0 };

        print!("{} ", is_selected);
    }

    print!("\n");
}

fn greedy_by_value_density(knapsack: &Knapsack) -> Result<SackContent, String> {
    let mut sorted_items: Vec<Item> = knapsack.items().iter().map(|x| x.clone()).collect();

    let mut sack_content = SackContent::new(knapsack.capacity);

    sorted_items.sort_by(|a, b| b.value_density.partial_cmp(&a.value_density).unwrap());

    for item in sorted_items.iter() {
        if !sack_content.has_space() {
            break;
        }

        if sack_content.can_fit(item) {
            sack_content.add_item(item);
        }
    }

    Ok(sack_content)
}

#[derive(Debug)]
struct SackContent {
    objective: u64,
    weight_limit: u64,
    weight: u64,
    selected_ids: Vec<usize>,
}

impl SackContent {
    pub fn new(weight_limit: u64) -> Self {
        SackContent {
            objective: 0,
            weight: 0,
            selected_ids: vec![],
            weight_limit,
        }
    }

    pub fn add_item(&mut self, item: &Item) {
        self.objective += item.value * item.weight; // TODO: may overflow
        self.weight += item.weight;
        self.selected_ids.push(item.id);
    }

    pub fn can_fit(&self, item: &Item) -> bool {
        self.weight + item.weight <= self.weight_limit
    }

    pub fn has_space(&self) -> bool {
        self.weight < self.weight_limit
    }

    pub fn contains(&self, item: &Item) -> bool {
        self.selected_ids.contains(&item.id)
    }
}

#[derive(Debug)]
struct Knapsack {
    pub capacity: u64,
    items: Vec<Item>,
}

impl Knapsack {
    pub fn new(capacity: u64, items: Vec<Item>) -> Self {
        Knapsack { capacity, items }
    }

    pub fn items(&self) -> &[Item] {
        self.items.as_slice()
    }
}

#[derive(Clone, Debug)]
struct Item {
    pub id: usize,
    pub value: u64,
    pub weight: u64,
    value_density: f64,
}

impl Item {
    pub fn new(id: usize, value: u64, weight: u64) -> Self {
        Item {
            id,
            value,
            weight,
            value_density: (value as f64 / weight as f64),
        }
    }
}

fn read_items(rows: usize) -> Vec<Item> {
    let mut items: Vec<Item> = Vec::with_capacity(rows);

    for item_id in 0..rows {
        let row = read_vector::<u64>();
        items.push(Item::new(item_id, row[0], row[1]));
    }

    items.shrink_to_fit();
    items
}

fn read_vector<T>() -> Vec<T>
where
    T: FromStr,
    T::Err: Debug,
{
    let buf = read_string();

    let res: Vec<T> = buf
        .trim()
        .split_whitespace()
        .map(|token| token.parse::<T>().expect("failed to parse vector row"))
        .collect();

    res
}

fn read_string() -> String {
    let mut buf = String::new();

    std::io::stdin()
        .read_line(&mut buf)
        .expect("Failed to read string from stdin");

    buf
}