登录
  • #刷题

求解一道NP complete变polynomial算法题

猪头小队长w
833
5
给一个数组L和数字k,数组L的每个element加起来sum是n

已知 n/2 <= k <= n

需要输出if there exists a subset of L that sums to k. in polynomial time.

而且这道题给了一个可以用的magical function 输入可以是任意数组,output出 if there’s a subset that sums up to n,n为数组总和的一半。假设这个function time complexity是O(1)

感觉如果没给那个可以用的function这道题应该是NP complete。但不知道如何利用这个function达到polynomial time……请教各位大佬 谢谢大家
5条回复
热度排序

发表回复