\(I = [0,n), a \in Z^{I}\), \(a(i) \geq 0 \text{ } \forall i \in I\), \(w \in Z\), \(w \geq 0\)
\(F_{I,a,w}=\{J \mid J \subseteq I, \sum_{i \in J} a(i) \leq w)\)
What is \(|F_{I,a,w}|\)?
\(F_{I,a,w}^{'}=\{J \mid J \subseteq I, \sum_{i \in J} a(i) = w)\)
\(F_{I,a,w} = \cup_{w^{'}\leq w} F_{I,a,w^{'}}^{'}\)
If \(J_0 \subseteq J_1 \subseteq \dots \subseteq I\) is a chain, then \(F_{J_0,a,w}^{'} \subseteq F_{J_1,a,w}^{'} \subseteq \dots \subseteq F_{I,a,w}^{'}\) is also a chain.
Let \(J_i=[0,i)\). Then, \(J_0=[0,0)=\emptyset\) and \(I = J_{n}=[0,n)\)
\(|F_{\emptyset,a,0}^{'}|=1\) and if \(w > 0\), then \(|F_{\emptyset,a,w}^{'}|=0\)
\(|F_{J_{i},a,w}^{'}|=|F_{J_{i-1},a,w}^{'}|+|F_{J_{i-1},a,w-a(i)}^{'}|\)
\(|F_{I,a,w}|=\sum_{w^{'}\leq w} |F_{I,a,w}^{'}|\)
A simple dynamic programming counting scheme over \(i\) and \(w^{'}\) follows. I already wrote the code to do this before solving the problem in this manner: read further on to see it.
If you fix \(J\), then \(|F_{J,a,w}^{'}|\) is a total function of w. Now, I can express \(|F_{I,a,w}|\) as a summation over a convolution:
\(|F_{I,a,w}|=\sum_{w^{'}=0}^{w}|F_{\emptyset,a,w^{'}}^{'}|*|F_{\{a(0)\},a,w^{'}}^{'}|*\dots * |F_{\{a(n-1)\},a,w^{'}}^{'}|\)
You can arrive at the convolution with generating functions, but I have a signal processing intuition for this: the elements of the convolutions are basically linear two-tap forward echo filters and applying the recurrence is just performing a sparse convolution. Even if you didn’t know that, a subtle clue that such a counting scheme is possible is that \(|F_{I,a,w}|\) is symmetric with respect to the order of the elements in the sequence \(a\); and, convolution is commutative. I think the convolution form might lend itself to a faster divide and conquer computation for large \(w\). You could also perform the convolutions with the fast Fourier transform over a finite field. Still, the filters are quite sparse at the beginning. I’ll look into the complexity and asymptotics of this all later.
Supposedly, there’s other counting schemes for this. I’m not surprised. This problem has a particular geometry to it as well because the constraint on the set system is that of the 0-1 knapsack problem. Also, I think there might be something to do with representing the linear terms over the underlying set of the sequence \(a\) as multisets. Again, I’ll look more into this later.
Also, I thought of another problem for later while solving this one. If \(F_{I,a,w}\) is an independence system over a finite \(I\), then it’s equal to the union of its maximal elements. How do you count or enumerate those elements?
#include<iostream>
#include<vector>
#include<cassert>
int main() {
int n;
int W;
std::cin >> n;
std::cin >> W;
assert(W >= 0);
std::vector<int> a(n); // sequence a
int i = 0;
while (i < n) {
int a_i;
std::cin >> a_i;
assert(a_i >= 0);
a[i] = a_i;
i = i + 1;
}
std::vector<long long> count_F(W + 1);
count_F[0] = 1;
i = 0;
while (i < n) {
int w = W;
while (w >= a[i]) {
if (w - a[i] >= 0) {
count_F[w] = count_F[w] + count_F[w - a[i]];
}
w = w - 1;
}
i = i + 1;
}
long long count = 0;
int w = 0;
while (w <= W) {
std::cout << count_F[w] << std::endl;
count = count + count_F[w];
w = w + 1;
}
std::cout << count << std::endl;
}