haar_lib/algo/knapsack/
limited.rs1use crate::{chmax, num::one_zero::Zero};
3use std::{
4 cmp::min,
5 ops::{Add, Mul},
6};
7
8pub 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}