結果

問題 No.2364 Knapsack Problem
ユーザー atcoder8atcoder8
提出日時 2023-06-30 23:35:12
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,779 ms / 3,000 ms
コード長 3,625 bytes
コンパイル時間 12,407 ms
コンパイル使用メモリ 383,924 KB
実行使用メモリ 128,132 KB
最終ジャッジ日時 2024-07-07 11:28:05
合計ジャッジ時間 25,393 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 245 ms
33,424 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 27 ms
5,920 KB
testcase_10 AC 126 ms
17,696 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 1,135 ms
128,004 KB
testcase_13 AC 974 ms
128,004 KB
testcase_14 AC 555 ms
64,972 KB
testcase_15 AC 1,553 ms
128,004 KB
testcase_16 AC 1,014 ms
128,132 KB
testcase_17 AC 842 ms
128,008 KB
testcase_18 AC 1,099 ms
127,928 KB
testcase_19 AC 1,779 ms
128,128 KB
testcase_20 AC 1,640 ms
128,004 KB
testcase_21 AC 920 ms
128,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashMap;

fn main() {
    let input = Input::read();

    let mut memo = HashMap::new();
    let ans = rec(&input, 0, 0, 0, 0, &mut memo);
    println!("{}", ans);
}

fn rec(
    input: &Input,
    used_products: usize,
    used_magics: usize,
    w: i64,
    v: i64,
    memo: &mut HashMap<(usize, usize, i64, i64), i64>,
) -> i64 {
    if w < 0 || w > input.weight_limit {
        return 0;
    }

    if let Some(&sum_v) = memo.get(&(used_products, used_magics, w, v)) {
        return sum_v;
    }

    let mut max_value = v;

    for product in 0..input.product_num {
        if (used_products >> product) & 1 == 1 {
            continue;
        }

        let next_used_products = used_products | (1 << product);

        let value1 = rec(input, next_used_products, used_magics, w, v, memo);
        let value2 = rec(
            input,
            next_used_products,
            used_magics,
            w + input.weights[product],
            v + input.values[product],
            memo,
        );
        max_value = max_value.max(value1).max(value2);
    }

    for magic in 0..input.magic_num {
        if (used_magics >> magic) & 1 == 1 {
            continue;
        }

        let next_used_magics = used_magics | (1 << magic);

        let value1 = rec(input, used_products, next_used_magics, w, v, memo);
        let value2 = rec(
            input,
            used_products,
            next_used_magics,
            w - input.reduce_weight[magic],
            v - input.reduce_value[magic],
            memo,
        );
        max_value = max_value.max(value1).max(value2);
    }

    memo.insert((used_products, used_magics, w, v), max_value);

    max_value
}

struct Input {
    product_num: usize,
    magic_num: usize,
    weights: Vec<i64>,
    values: Vec<i64>,
    weight_limit: i64,
    reduce_weight: Vec<i64>,
    reduce_value: Vec<i64>,
}

impl Input {
    fn read() -> Self {
        let (product_num, magic_num, weight_limit) = {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                iter.next().unwrap().parse::<usize>().unwrap(),
                iter.next().unwrap().parse::<usize>().unwrap(),
                iter.next().unwrap().parse::<i64>().unwrap(),
            )
        };
        let weights: Vec<_> = {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|x| x.parse::<i64>().unwrap())
                .collect()
        };
        let values: Vec<_> = {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|x| x.parse::<i64>().unwrap())
                .collect()
        };
        let reduce_weight: Vec<_> = {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|x| x.parse::<i64>().unwrap())
                .collect()
        };
        let reduce_value: Vec<_> = {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|x| x.parse::<i64>().unwrap())
                .collect()
        };

        Self {
            product_num,
            magic_num,
            weights,
            values,
            weight_limit,
            reduce_weight,
            reduce_value,
        }
    }
}
0