3
\$\begingroup\$

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"),
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Your indentation seems off. Is that the same indentation you've used in your program? \$\endgroup\$
    – Zeta
    Mar 3 '18 at 16:59
  • \$\begingroup\$ Should be better now \$\endgroup\$
    – A. Romeu
    Mar 3 '18 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.