haar_lib/algo/knapsack/
small_value.rs

1//! 価値の総和が小さいナップサック問題
2use crate::chmin;
3
4/// 価値の総和が小さいナップサック問題
5///
6/// **Time complexity** $O(n \sum vs)$
7///
8/// **Space complexity** $O(\sum vs)$
9pub fn knapsack_small_value(cap: u64, ws: &[u64], vs: &[usize]) -> usize {
10    let n = ws.len();
11    assert_eq!(ws.len(), vs.len());
12
13    let max_v = vs.iter().sum::<usize>();
14    let mut dp = vec![vec![u64::MAX; max_v + 1]; 2];
15
16    dp[0][0] = 0;
17
18    for i in 0..n {
19        let next = (i + 1) & 1;
20        let cur = i & 1;
21        for j in 0..=max_v {
22            chmin!(dp[next][j], dp[cur][j]);
23            if j + vs[i] <= max_v && dp[cur][j] < u64::MAX {
24                chmin!(dp[next][j + vs[i]], dp[cur][j] + ws[i]);
25            }
26        }
27    }
28
29    dp[n & 1]
30        .iter()
31        .enumerate()
32        .rev()
33        .find(|(_, &x)| x <= cap)
34        .unwrap()
35        .0
36}