<p>Here's a potential (but incomplete) answer.</p>
<p>Choose <span class="math-container">$a_n = \frac{1}{n}$</span>. Let <span class="math-container">$\tau$</span> be the capacity of the knapsack. Then a lower bound on the number of feasible solutions is given by</p>
<p><span class="math-container">$$F(n) \geq 2^{N (1-\frac{1}{e^{\tau}})}.$$</span></p>
<p>To see this, note that
<span class="math-container">$$\frac{1}{\frac{N}{e^{\tau}}}  + ... + \frac{1}{N} \approx \log N - \log \frac{N}{e^{\tau}} = \tau.$$</span></p>
<p>Thus, any subset <span class="math-container">$S \subset \{\frac{N}{e^{\tau}},...,N\}$</span> is a feasible solution to the Knapsack problem given above. This yields at least <span class="math-container">$2^{N (1-\frac{1}{e^{\tau}})}$</span> feasible solutions.</p>
<p>To complete this, it suffices to show that this lower bound is tight.</p>
<p>I'm not sure if this direction is right, but it is important to note that any feasible set must have at most <span class="math-container">$N (1-\frac{1}{e^{\tau}})$</span> elements. Therefore, we have
<span class="math-container">$$F(N) \leq \sum_{i=1}^{N} \binom{N}{N (1-\frac{1}{e^{\tau}})}.$$</span></p>

CC BY-SA 4.0
2022-04-22T18:24:52.830Z
I doubt $2^{N(1-e^{-\tau})}$ is tight. For $\tau = 1$ for ease, it seems a random subset of $[e^{-2}N,N]$ of density $\frac{1}{2}$ (i.e., of size $\frac{1}{2}(1-e^{-2})N$) should work. And there are basically $2^{N(1-e^{-2})}$ of these sets.
mathworker21
CC BY-SA 4.0
2022-04-21T20:36:50.170Z
2022-04-21T21:42:25.397Z
2022-04-21T21:42:25.397Z
Asterix
<p>It is possible I missed some additional constraint... but you could simply let <span class="math-container">$a_n=2^{n-1}$</span> so that every possible number in {0,...,2^n-1} is attainable via a unique subset of <span class="math-container">$a_1,...,a_n$</span>, then set <span class="math-container">$\tau$</span> to be <span class="math-container">$2^{\alpha n}-1$</span>. If <span class="math-container">$\tau$</span> has to be a fixed  constant, divide all the above by <span class="math-container">$2^{\alpha n}-1$</span>. Note for <em>any</em> possible growth rate <span class="math-container">$F(n)$</span>, you could do the same thing.</p>

CC BY-SA 4.0
2022-04-22T14:18:28.357Z
2022-04-22T14:18:28.357Z
Ryan Williams
<p>Let's say I have a Knapsack with capacity <span class="math-container">$\tau$</span>, and I have an infinite sequence of items with weights <span class="math-container">$(a_n)_{n=1}^{\infty}$</span>. A feasible Knapsack solution is a subset <span class="math-container">$S \subset \mathbb{N}$</span> such that  <span class="math-container">$\sum_{i \in S} a_i \leq \tau.$</span> Define the number of feasible solutions which use the first <span class="math-container">$n$</span> items as <span class="math-container">$F(n) = \# \{S \subset \{1,...,n\} : S \text{ is feasible}\}.$</span></p>
<p>Are there known results on the growth rate of <span class="math-container">$F(n)$</span> as a function of the sequence <span class="math-container">$(a_n)_{n=1}^{\infty}$</span>?</p>
<p>For example, there is a lower bound <span class="math-container">$L &gt; 0$</span> such that <span class="math-container">$a_n \geq L$</span> for all <span class="math-container">$L$</span>, then any feasible solution <span class="math-container">$S$</span> must have at most <span class="math-container">$\lceil \frac{\tau}{L} \rceil$</span> elements, and <span class="math-container">$|F(n)| \leq \sum_{i=0}^{\lceil \frac{\tau}{L} \rceil} \binom{n}{i}.$</span> Since <span class="math-container">$L$</span> is a constant, this means that the growth rate of <span class="math-container">$F(n)$</span> is at most polynomial in <span class="math-container">$n$</span>.</p>
<p>On the other hand, if <span class="math-container">$a_n = \frac{\tau}{2^n}$</span>, then <span class="math-container">$\sum_{i=1}^{\infty} a_i \leq \tau$</span>, so any set <span class="math-container">$S$</span> is a feasible knapsack solution. This means that <span class="math-container">$F(n) = 2^n$</span>.</p>
<p>Are there any intermediate sequences <span class="math-container">$(a_n)$</span> such that <span class="math-container">$F(n) = 2^{\alpha n}$</span> for some <span class="math-container">$\alpha$</span>?  There's of course some ways to &quot;cheat&quot; and say something like
<span class="math-container">$$a_n = \begin{cases} \frac{1}{2^n} \text{ if } n \text{ is even} \\ 1 \text{ if } n \text{ is odd.} \end{cases}$$</span></p>
<p>I'm looking for a somewhat more natural sequence.</p>

<optimization><counting-complexity>
Growth rate of Knapsack Solutions
Asterix
# Growth rate of Knapsack Solutions

(Asked by: username_0 on 2022-04-21)

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.

**Tags:** optimization, counting-complexity


---

## 2 answers

### Answer by username_0 on 2022-04-21. Score: 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}})}.$$

> **Comments:**
> **username_1**: I doubt $2^{N(1-e^{-\tau})}$ is tight. For $\tau = 1$ for ease, it seems a random subset of $[e^{-2}N,N]$ of density $\frac{1}{2}$ (i.e., of size $\frac{1}{2}(1-e^{-2})N$) should work. And there are basically $2^{N(1-e^{-2})}$ of these sets.  

---

### Answer by username_2 on 2022-04-22. Score: 1

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.


---

