We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for the #P-complete problem of counting 0/1 Knapsack solutions, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes in (Gopalan et al., FOCS 2011), (Stefankovic et al., SIAM J. Comput. 2012) and the randomized counting and random generation algorithms in (Dyer, STOC 2003). We also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.
展开▼
机译：对于计数0/1背包解的＃P-完全问题及其随机代，我们给出了更快，更简单的完全多项式时间近似方案（FPTASes）。我们的方法基于动态编程，并通过浮点算法对大量数字进行离散化。我们改进了（Gopalan等人，FOCS 2011）（Stefankovic等人，SIAM J. Comput。2012）中的确定性计数FPTASes和（Dyer，STOC 2003）中的随机计数和随机生成算法。我们还提高了在弧加权DAG中计算0/1背包解决方案的问题的复杂性。
展开▼
