haar_lib/algo/subset_sum/
limited.rs

1//! 各要素に最大使用回数が定められている部分和問題
2
3/// 各要素に最大使用回数が定められている部分和問題
4///
5/// **Time complexity** $O(nk)$
6///
7/// **Space complexity** $O(k)$
8///
9/// # Arguments
10///
11/// * `n` - 要素数 (`== a.len()`, `== m.len()`)
12/// * `k` - 判定したい値の最大値 (0以上k以下の整数について部分和が構成できるかを判定する。)
13/// * `a` - 総和をとる数列。
14/// * `m` - `m[i]`は`a[i]`を使用できる最大回数。
15pub fn subset_sum_limited(n: usize, k: usize, a: &[usize], m: &[usize]) -> Vec<bool> {
16    assert!(a.len() == n);
17    assert!(m.len() == n);
18
19    let mut dp: Vec<isize> = vec![-1; k + 1];
20
21    dp[0] = 0;
22    for i in 0..n {
23        for j in 0..=k {
24            if dp[j] >= 0 {
25                dp[j] = m[i] as isize;
26            } else if j < a[i] || dp[j - a[i]] <= 0 {
27                dp[j] = -1;
28            } else {
29                dp[j] = dp[j - a[i]] - 1;
30            }
31        }
32    }
33
34    dp.into_iter().map(|x| x >= 0).collect()
35}
haar_lib/algo/subset_sum/limited.rs

haar_lib/algo/subset_sum/
limited.rs
