Bibliography needed: How many "good" solutions for Knapsack?
Shooting from the hip here, but I think this might, in fact, be a simple problem to solve in pseudopolynomial time, using dynamic programming (DP). Not sure if that's acceptable, or if you need a polynomial-time algorithm?


  A brief detour: You assume that the optimal value is known, and that $\varepsilon&gt;0$, and I don't know how hard the given counting problem is. If you made no such assumptions, however, you're basically left with (an obvious reduction from) the decision-version of 0-1-knapsack, which is, of course, NP-complete. The question, of course, is whether the additional assumptions are enough to “rescue” the problem from hardness.


My intuition comes from the fact that DP formulations in general are equivalent to path problems (such as shortest/longest path, or the number of paths) in DAGs. I think counting the number of paths from some node $s$ (representing the zero-capacity knapsack and the empty subset of items) that are “long enough,” given some threshold (in your case, $(1-\varepsilon)v$) is quite straightforward as well.

You can formulate it recursively, as follows. Let $G=(V,E)$ be your DAG, let $w(u,v)$ be the edge weight function, let $\ell_\delta(v)$ be the number of $s$-paths ending at node $v$ with a length of at least $\delta$. You then have:

\begin{equation}
\ell_\delta(v) =
\begin{cases}
0 &amp; \text{if $v=s \land \delta &gt; 0\,$;} \\
1 &amp; \text{if $v=s \land \delta \leq 0\,$;} \\
\sum_{u:(u,v)\in E} \ell_{\delta-w(u,v)}(u)&amp; \text{otherwise.}
\end{cases}
\end{equation}

I'm implicitly assuming that all nodes lie on a path from $s$, as they will in your case, but for nodes beside $s$ that don't have predecessors, the sum will simply be an empty sum, which can be assumed to be zero. To implement this, just memoize it or turn it “upside down” and fill the appropriate array.

In the knapsack case, you'd only have two predecessors $u$ to sum over, of course (i.e., the ones representing the solutions with and without the object under consideration in node $v$). The solution will simply be $\ell_{(1-\varepsilon)v}(t)$, where $t$ is the final “corner” of your matrix, with full capacity and the full set of items.