4
\$\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, 2018 at 16:59
  • \$\begingroup\$ Should be better now \$\endgroup\$
    – A. Romeu
    Mar 3, 2018 at 17:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.