PolynomialSubsetSum子集和问题的多项式时间算法探索
子集求和问题是一项挑战,为解决这一问题,本项目致力于实现强多项式算法。在这个代码库中,您将找到一系列多项式时间算法的实现,不断优化子集和问题的解法。请注意:本项目的repo最终可能会包含多种算法实现。本自述文件仅适用于目前正在探索的方法。当前实现的big-O运行时间为 O(n^7)。
主要文件和实现说明如下:
-
RefactoredSubsetSum.java:经过优化的实现版本,其中的算法基于在
method.pdf
中给出的封闭形式,经过了一定的推论分析。 -
SubsetSum.java:该文件是原始实现,使用矩阵及矩阵运算构建算法的基本框架。
本项目保持动态发展,进一步优化性能和探索多种实现途径。如果您使用了这些代码或算法,非常棒!一些引用表示非常感谢。如果您在使用中发现问题或改进之道,欢迎联系我分享您的发现!请注意:此算法在 n = 200 的规模上已进行测试,运行表现也在不断优化中。
下载地址
用户评论