haar_lib/algo/knapsack/
limited.rs

1//! 個数制限付きナップサック問題
2use crate::{chmax, num::one_zero::Zero};
3use std::{
4    cmp::min,
5    ops::{Add, Mul},
6};
7
8/// 個数制限付きナップサック問題
9///
10/// **Time complexity** $O(n \cdot cap \log \max ms)$
11///
12/// **Space complexity** $O(cap)$
13pub fn knapsack_limited<T>(cap: usize, ws: &[usize], vs: &[T], ms: &[usize]) -> T
14where
15    T: Copy + Ord + Add<Output = T> + Mul<Output = T> + Zero + From<usize>,
16{
17    let n = ws.len();
18    assert!(vs.len() == n && ms.len() == n);
19    let mut dp = vec![T::zero(); cap + 1];
20
21    for i in 0..n {
22        let mut a = 1;
23        let mut x = ms[i];
24        while x > 0 {
25            let k = min(x, a);
26
27            for j in (0..=cap).rev() {
28                if j >= k * ws[i] {
29                    chmax!(dp[j], dp[j - k * ws[i]] + T::from(k) * vs[i]);
30                }
31            }
32
33            x -= k;
34            a *= 2;
35        }
36    }
37
38    dp[cap]
39}