Growth rate of Knapsack Solutions

Question

Let's say I have a Knapsack with capacity $\tau$, and I have an infinite sequence of items with weights $(a_n)_{n=1}^{\infty}$. A feasible Knapsack solution is a subset $S \subset \mathbb{N}$ such that $\sum_{i \in S} a_i \leq \tau.$ Define the number of feasible solutions which use the first $n$ items as $F(n) = \# \{S \subset \{1,...,n\} : S \text{ is feasible}\}.$

Are there known results on the growth rate of $F(n)$ as a function of the sequence $(a_n)_{n=1}^{\infty}$?

For example, there is a lower bound $L > 0$ such that $a_n \geq L$ for all $L$, then any feasible solution $S$ must have at most $\lceil \frac{\tau}{L} \rceil$ elements, and $|F(n)| \leq \sum_{i=0}^{\lceil \frac{\tau}{L} \rceil} \binom{n}{i}.$ Since $L$ is a constant, this means that the growth rate of $F(n)$ is at most polynomial in $n$.

On the other hand, if $a_n = \frac{\tau}{2^n}$, then $\sum_{i=1}^{\infty} a_i \leq \tau$, so any set $S$ is a feasible knapsack solution. This means that $F(n) = 2^n$.

Are there any intermediate sequences $(a_n)$ such that $F(n) = 2^{\alpha n}$ for some $\alpha$? There's of course some ways to "cheat" and say something like $$a_n = \begin{cases} \frac{1}{2^n} \text{ if } n \text{ is even} \\ 1 \text{ if } n \text{ is odd.} \end{cases}$$

I'm looking for a somewhat more natural sequence.

Answer 1

Here's a potential (but incomplete) answer.

Choose $a_n = \frac{1}{n}$. Let $\tau$ be the capacity of the knapsack. Then a lower bound on the number of feasible solutions is given by

$$F(n) \geq 2^{N (1-\frac{1}{e^{\tau}})}.$$

To see this, note that $$\frac{1}{\frac{N}{e^{\tau}}} + ... + \frac{1}{N} \approx \log N - \log \frac{N}{e^{\tau}} = \tau.$$

Thus, any subset $S \subset \{\frac{N}{e^{\tau}},...,N\}$ is a feasible solution to the Knapsack problem given above. This yields at least $2^{N (1-\frac{1}{e^{\tau}})}$ feasible solutions.

To complete this, it suffices to show that this lower bound is tight.

I'm not sure if this direction is right, but it is important to note that any feasible set must have at most $N (1-\frac{1}{e^{\tau}})$ elements. Therefore, we have $$F(N) \leq \sum_{i=1}^{N} \binom{N}{N (1-\frac{1}{e^{\tau}})}.$$

Answer 2

It is possible I missed some additional constraint... but you could simply let $a_n=2^{n-1}$ so that every possible number in {0,...,2^n-1} is attainable via a unique subset of $a_1,...,a_n$, then set $\tau$ to be $2^{\alpha n}-1$. If $\tau$ has to be a fixed constant, divide all the above by $2^{\alpha n}-1$. Note for any possible growth rate $F(n)$, you could do the same thing.