-
0 votesanswersviews
返回N个正数中从大小1到L的最大不相交和连续子集
我试图概括Paul Hankin在_640672中提供的算法,这样解决方案不仅限于每个子集的大小都是L,并且目标不是最大化总和,而是返回具有最大子集的集合 . 详细说明, X 是一组 N 正实数: X={x[1],x[2],...x[N]} where x[j]>=0 for all j=1,...,N . 一个名为 S[i] 的连续子集由 up to L X 的连续成员组成,从 ... -
966 votesanswersviews
NP,NP-Complete和NP-Hard有什么区别?
NP , NP-Complete 和 NP-Hard 之间有什么区别? 我知道网上有很多资源 . 我想阅读你的解释,原因是它们可能与那里有什么不同,或者它在那里,我不知道 . -
1 votesanswersviews
一些NP-Complete问题怎么也是NP-Hard?
我正在尝试以一种直观的方式将我听到的P,NP,NP-Complete和NP-Hard包裹起来,以便我不必记住他们的定义 . 在下图中(左手方案,P!= NP),NP-Complete和NP-Hard之间存在重叠区域 . 这是否意味着一些问题既是NP-Complete又是NP-Hard?根据这个特殊答案,我发现这是矛盾的:What are the differences between NP, NP... -
1 votesanswersviews
NP-complete与NP-hard(为什么它们不相等?)
为什么NP-hard不等于NP-complete? My informal understanding of definitions being used: NP - 可以在多项式时间内验证的所有问题 NP完全 - 所有NP和NP难的问题 NP-hard - 至少和NP中最难的问题一样难 决策问题 - 询问有关输入的问题并输出bool值的问题 Confusion: P与NP未知解的问题源于这样... -
1 votesanswersviews
子集和问题的有趣变化
一位朋友从工作中向我展示了一个有趣的子集和问题变体: 给定S的正整数,大小为n,以及整数a和K,是否存在包含 exactly a elements 的子集R(集合S),其总和等于K? 他声称这可以用时间复杂度O(nka)来完成,我无法想出一个能够实现这个运行时间的动态编程算法 . 可以吗?