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