Here is an implementation of Knapsack in Rust. How could it be improved? Some things I have already spotted:
What would be the best way to extract result? Is using an option preferred unwrapping the last element of vector? I also want to show last value of vector regardless of its contents, so would unwrapping be preferable?
How to save casting all the time for array indices, vector definitions?
use std::cmp;
fn solve_knapsack_dynamically(
weights: &Vec<i64>,
profits: &Vec<i64>,
knap_sack_max_weight: i64,
) -> Option<i64> {
let mut prev_row = vec![0; knap_sack_max_weight as usize];
let mut curr_row = vec![0; knap_sack_max_weight as usize];
for i in 1..weights.len() {
for j in 0..knap_sack_max_weight {
if weights[i as usize] > j {
curr_row[j as usize] = prev_row[j as usize];
} else {
curr_row[j as usize] = cmp::max(
prev_row[j as usize],
prev_row[(j - weights[i as usize]) as usize] + profits[i as usize],
);
}
}
prev_row = curr_row.to_vec();
}
curr_row.last().cloned()
}
fn main() {
let weights = vec![10, 50, 20, 100];
let profits = vec![56, 23, 11, 4];
let knap_sack_max_weight = 120;
let result = solve_knapsack_dynamically(&weights, &profits, knap_sack_max_weight);
match result {
Some(x) => println!("Result: {}", x),
None => println!("Failed"),
}
}