アルゴリズムと数学 030

https://atcoder.jp/contests/math-and-algorithm/tasks/dp_d

重さを状態とするDPですね。

// Knapsack 1
#![allow(non_snake_case)]

use std::cmp::max;

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_input() -> (usize, Vec<(usize, i64)>) {
    let v = read_vec();
    let N: usize = v[0];
    let W: usize = v[1];
    let goods: Vec<(usize, i64)> = (0..N).map(|_| read_vec()).
                                        map(|v| (v[0], v[1] as i64)).collect();
    (W, goods)
}

fn update(dp: Vec<i64>, w: usize, v: i64) -> Vec<i64> {
    let mut new_dp = dp.to_vec();
    new_dp[w] = max(new_dp[w], v);
    for (w0, v0) in dp.into_iter().enumerate() {
        if v0 > 0 && w0 + w < new_dp.len() {
            new_dp[w0+w] = max(new_dp[w0+w], v0 + v)
        }
    }
    new_dp
}

fn f(W: usize, goods: Vec<(usize, i64)>) -> i64 {
    let mut dp = (0..W+1).map(|_| 0).collect::<Vec<i64>>();
    for (w, v) in goods.into_iter() {
        dp = update(dp, w, v)
    }
    dp.into_iter().max().unwrap()
}

fn main() {
    let (W, goods) = read_input();
    println!("{}", f(W, goods))
}