Ранец 0-1 в Русте


Вот это реализация рюкзак в Rust. Как это можно улучшить? Некоторые вещи я уже заметил:

Что бы быть лучшим способом, чтобы извлечь результат? С помощью предпочтительного варианта разворачивания последний элемент вектора? Я тоже хочу показать последнее значение вектора вне зависимости от его содержания, поэтому разворачивание будет предпочтительнее?

Как сохранить бросая все время для индексов массива, определения вектора?

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"),
    }
}


144
2
задан 3 марта 2018 в 04:03 Источник Поделиться
Комментарии