Computing sets of high quality solutions has gained increasing interest in recent years. In this paper, we investigate how to obtain sets of optimal solutions for the classical knapsack problem. We present an algorithm to count exactly the number of optima to a zero-one knapsack problem instance. In addition, we show how to efficiently sample uniformly at random from the set of all global optima. In our experimental study, we investigate how the number of optima develops for classical random benchmark instances dependent on their generator parameters. We find that the number of global optima can increase exponentially for practically relevant classes of instances with correlated weights and profits which poses a justification for the considered exact counting problem.
翻译:高品质的计算机解决方案组近年来引起了越来越多的兴趣。 在本文中, 我们调查了如何为古典的背包问题获得一套最佳解决方案。 我们提出了一个算法, 精确地计算opima数量到零1 knappsack问题实例。 此外, 我们展示了如何从全局的全局选择中统一地随机进行有效抽样。 在实验研究中, 我们研究Popima的数量如何发展出传统随机基准实例, 取决于其生成参数。 我们发现, 具有相关重量和利润的几乎相关的各类案例, 全球optima数量会成指数增长, 这为考虑的精确计算问题提供了理由 。