A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
Martin Dyer, ALAN M. FRIEZE, Ravi Kannan, Ajai Kapoor, Ljubomir Perković, Umesh V. Vazirani · Combinatorics Probability Computing · 1993
We describe a time randomized algorithm that estimates the number of feasible solutions of a multidimensional knapsack problem within 1 ± ε of the exact number. (Here r is the number of constraints and n is the number of integer variables.) The algorithm uses a Markov chain to generate an almost uniform random solution to the problem.