A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
Given n elements with nonnegative integer weights $w_1, \ldots, w_n$ and an integer capacity C, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most the given capacity. We give a deterministic algorithm that estimates the number …