hanozerdem/subset-sum-fptas-analysis

# 子集和 FPTAS 分析 本仓库包含了一项关于 Subset Sum 优化问题的 Python 研究，对比了精确的暴力求解器与基于修剪列表的 FPTAS，并进行了实验评估。 小组成员： - Han Özerdem ## 目录 - `src/subset_sum_project.py` — 精确的暴力求解器、基于修剪列表的 FPTAS、实例生成器以及实验运行程序。 - `data/` — 生成的功能、初始、质量和性能测试结果。 - `figures/` — 报告中使用的图表。 - `docs/subset-sum-fptas-report.pdf` — 匿名的最终报告。 - `notebooks/` — 实验的 notebook 版本。 ## 问题与算法 本项目求解 Subset Sum 的优化形式：在不超出目标值的前提下，最大化子集的总和。 - 精确的基准方法使用了带有剪枝的递归包含/排除搜索。 - 近似算法使用了带有可配置 `epsilon` 的基于修剪列表的 FPTAS。 ## 运行实验 建议使用 Python 3.10 或更高版本。 ``` python src/subset_sum_project.py --out data --epsilon 0.20 --repetitions 20 ``` 该命令将重新生成 `data/` 中的 CSV 文件和分析摘要。 ## 验证快照 包含的结果中有 8/8 个功能测试用例通过，最小质量比约为 0.988，并且有 7/7 行性能数据满足置信区间标准。

标签：FPTAS, NoSQL, Python, 子集和问题, 学术研究, 无后门, 算法, 近似算法, 逆向工具