Rustで貪欲法 (1)

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。7章の貪欲法。

今回は「コイン問題」

use proconio::input;

// コインの金額
const VALUE: [u64; 6] = [500, 100, 50, 10, 5, 1];

fn input(use_default_values: bool) -> (u64, Vec<u64>) {
    if use_default_values {
        let x = 123;
        let a = vec![1, 1, 1, 1, 5, 5];
        return (x, a);
    } else {
        println!("Input x and a:");
        input! {
            x: u64,
            a: [u64; 6],
        }
        return (x, a);
    }
}

/// コイン問題を解く貪欲法
pub fn code_7_1(use_default_values: bool) -> u64 {
    // 入力
    let (mut x, a) = input(use_default_values);

    // 貪欲法
    let mut result = 0;
    for i in 0..6 as usize {
        // 枚数制限がない場合の枚数
        let mut add = x / VALUE[i];

        // 枚数制限を考慮
        if add > a[i] {
            add = a[i];
        }

        // 残り金額を求めて，答えに枚数を加算する
        x -= VALUE[i] * add;
        result += add;
    }
    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn code_7_1_works() {
        assert_eq!(code_7_1(true), 7);
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust