haar_lib/algo/knapsack/
small_weight.rs

1//! 容量が小さいナップサック問題
2use crate::{chmax, num::one_zero::Zero};
3use std::ops::Add;
4
5/// 容量が小さいナップサック問題
6///
7/// **Time complexity** $O(n \cdot cap)$
8///
9/// **Space complexity** $O(cap)$
10pub fn knapsack_small_weight<T>(cap: usize, ws: &[usize], vs: &[T]) -> T
11where
12    T: Copy + Ord + Add<Output = T> + Zero,
13{
14    let n = ws.len();
15    assert_eq!(ws.len(), vs.len());
16
17    let mut dp = vec![vec![T::zero(); cap + 1]; 2];
18
19    for i in 0..n {
20        let next = (i + 1) & 1;
21        let cur = i & 1;
22        for j in 0..=cap {
23            chmax!(dp[next][j], dp[cur][j]);
24            if j + ws[i] <= cap {
25                chmax!(dp[next][j + ws[i]], dp[cur][j] + vs[i]);
26            }
27        }
28    }
29
30    dp[n & 1][cap]
31}