这是我最近面临的一个编程挑战。
给你一个小于1000的数,你需要确定需要多少个最小数目的素数,这个数之和是给定的数。,
,You,you,of,你需要确定需要多少个最小数目的素数。
示例:
12: 2(自12=7+5开始) 14: 2(自14 = 7+7)
如果不可能将给定的数拆分为质数和,则返回-1。
以下是一些测试用例:
88:2 117:3 374:2 363:3 11:1
发布于 2019-06-19 02:27:18
这只是经典knapsack problem的一个变体。
在最初的背包问题和这个问题中,我们都有一组可以选择的项目。每一项都有它的成本/价值,我们正在优化它,并且它有一个我们受其限制的大小。在最初的背包问题中,我们希望最大化利润,同时将权重保持在设定的最大值之下。在这里,我们想要最小化素数的数量,而和恰好是我们给定的数量。
我们可以更改DP数组的定义,使DP[i][j]
是仅使用第一个i
素数和到j
所需的最小素数,或者如果仅使用第一个i
素数不可能求和到j
,则无穷大,并且我们的递归关系变为DP[i][j] = min(DP[i - 1][j], DP[i][j - p[i]] + 1)
,其中p[i]
是第i
个素数。然后,可以通过计算DP
表中的所有值或使用类似于原始背包问题的记忆法来计算DP[numPrimes][N]
。
正如Willem Van Onsem指出的那样,这个问题是一个特例,因为每个小于4* 10^18的偶数都可以表示为两个素数的和,这允许一个更快的解决方案,其复杂性与用于测试素数的算法相同。
https://stackoverflow.com/questions/56654738
复制相似问题