# A Faster FPTAS for #Knapsack

arXiv: https://arxiv.org/abs/1802.05791 · HTML: https://mlsanity.com/paper/1802.05791/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2018.

## Built on by (most cited first, 2 of 2)

- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)

## Abstract (arXiv)

Given a set W = w1,ldots, wn of non-negative integer weights and an integer C, the #Knapsack problem asks to count the number of distinct subsets of W whose total weight is at most C. In the more general integer version of the problem, the subsets are multisets. That is, we are also given a set  u1,ldots, un and we are allowed to take up to ui items of weight wi. We present a deterministic FPTAS for #Knapsack running in O(n2.5varepsilon-1.5log(n varepsilon-1)log (n varepsilon)) time. The previous best deterministic algorithm [FOCS 2011] runs in O(n3 varepsilon-1 log(nvarepsilon-1)) time (see also [ESA 2014] for a logarithmic factor improvement). The previous best randomized algorithm [STOC 2003] runs in O(n2.5 √log (nvarepsilon-1)  + varepsilon-2 n2 ) time. Therefore, in the natural setting of constant varepsilon, we close the gap between the tilde O(n2.5) randomized algorithm and the tilde O(n3) deterministic algorithm. For the integer version with U = maxi ui, we present a deterministic FPTAS running in O(n2.5varepsilon-1.5log(nvarepsilon-1 log U)log (n varepsilon) log2 U) time. The previous best deterministic algorithm [APPROX 2016] runs in O(n3varepsilon-1log(n varepsilon-1 log U) log2 U) time.