按年被提到
20152015 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:1507.02318 · cs.DS

A Faster Pseudopolynomial Time Algorithm for Subset Sum

更快的子集和伪多项式时间算法
Konstantinos Koiliaris, Chao Xu · 2015

给出比标准动态规划更快的子集和伪多项式算法

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2015-07-10 · 最近 2019-02-03发表于 ACM Transactions on Algorithms
3不同的人
3活跃月份
3讨论串
49被引(OpenAlex)

给定 n 个正整数的多重集合 S 和目标整数 t,论文提出一种分治算法,能在 Õ(min{√n·u, u^{4/3}, σ}) 时间内算出所有不超过 u 的可达子集和,优于标准动态规划的 O(nu),据作者所知是该问题最快的通用算法。作者还给出针对循环群的变体,在 Õ(min{√n·m, m^{5/4}}) 时间内算出群内所有可达的子集和。

HN 为什么提它

评论者引用它作为 2015 年子集和问题伪多项式时间算法的最新进展。

方法难度 5 / 5约 60 分钟经得起时间
读之前最好知道
1子集和问题与 NP 完全性
2动态规划(dynamic programming)
3分治算法
4伪多项式时间复杂度

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用visarga · 2017-11

“This arXiv paper shows the STOA from 2015:”

指出这篇 arXiv 论文给出了 2015 年的子集和问题最优算法
Adventures in Programming Interviews: Misleadingly Simple NP-Hard Problem原评论 ↗
被提交为 story · 2 次