In this paper we furnish quality certificates for the Divide-and-Conquer method solving the 0-1 Knapsack Problem: the worst case scenario and estimates for the expected performance. The probabilistic setting is given and the main random variables are defined for the analysis of the expected performance. The efficiency is rigorously approximated for one iteration of the method then, these values are used to derive analytic estimates for the performance of a general Divide-and-Conquer tree. All the theoretical results are verified with statistically suited numerical experiments for a wider illustration of the method.
翻译:在本文中,我们提供了解决0-1Knapsack问题的分化和收购方法的质量证书:最坏的假设情景和预期性能的估计。给出了概率环境,并定义了分析预期性能的主要随机变量。效率被严格地估计为当时方法的一个迭代,这些数值被用来为一般的分化和收购树的性能得出分析性估计。所有理论结果都经过统计上合适的数字实验来核实,以便更广泛地说明方法。