haar_lib/algo/knapsack/
unlimited.rs

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