1 2 3 4 567 / 7 页下一页

[算法] 搜狐2012牛逼笔试题，至今无思路，求牛人指点 [复制链接]

cjaizss

版主

论坛徽章:: 3

51楼 [报告]

发表于 2011-12-04 01:59 |只看该作者

本帖最后由 cjaizss 于 2011-12-04 02:49 编辑

回复 btdm123

首先装箱问题是NPC的，你的任何多项式算法一定有问题
你在缩小问题规模的时候 ...
hbmhalley 发表于 2011-12-04 00:40

首先这个问题本身就不是NPC,那是打死不动的比NPC更复杂的EXPTIME,任何多项式算法应该都不会是通用算法,如果真是,就nx了.真没想通怎么居然这么多乱回帖.
0/1背包才是NPC,
0/1背包是什么问题?
论域:{a1.....an,b}...a1...an,b都是自然数
问题:是否存在a1*j1+...an*jn=b(j1...jn在0,1中取)

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cjaizss

版主

论坛徽章:: 3

52楼 [报告]

发表于 2011-12-04 02:15 |只看该作者

本帖最后由 cjaizss 于 2011-12-04 03:07 编辑

首先这个问题本身就不是NPC,那是打死不动的比NPC更复杂的EXPTIME,任何多项式算法都不会是通用算法 ...
cjaizss 发表于 2011-12-04 01:59

什么是NPC?首先它是NP,不是NP,谈何NPC?对于这个问题,某人随便给你一组解,告诉你是最优的,你怎么判断这组就是最优的?你又重新回到了找最优解这个问题本身来了,判断问题和解决问题明显一样复杂.NP的意思是,判断问题的解答是否符合题意,只需要在多项式的步骤之内就可以解决.NPC的意思是最难解的NP,所谓最难解的NPC,就是说对于任何一个NP,暂且叫它A,任何一个NPC,叫B,都存在两个多项式算法C,D,使得C可以转换B问题的输入给A,A算法的输出再经过D就可以得到B问题的解答.
我们再回头看看0/1背包,为什么它是NP?(至于它是NPC我就不说了,要写一段证明,有时间有兴趣自己去翻计算理论)这个问题怎么解答很难,但人家只要给你一组解答,判断的时候只要加一遍再比较一下就搞定了,O(n)级别的判断

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cjaizss

版主

论坛徽章:: 3

53楼 [报告]

发表于 2011-12-04 02:24 |只看该作者

什么是NPC?首先它是NP,不是NP,谈何NPC?对于这个问题,某人随便给你一组解,告诉你是最优的,你怎么判 ...
cjaizss 发表于 2011-12-04 02:15

可能很多人都不明白这些定义吧.那么不明白就不要乱说.
P:多项式时间可解决
  NP:多项式时间可判断解是否切题
  转化:多项式时间内,从一个问题的出发可以得到另外一个问题的解答
  NPC:如果一个NP问题,使得所有的NP都可以转化成这个问题,那么称之为NPC,这是最难NP

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cjaizss

版主

论坛徽章:: 3

54楼 [报告]

发表于 2011-12-04 02:47 |只看该作者

本帖最后由 cjaizss 于 2011-12-04 03:26 编辑

可能很多人都不明白这些定义吧.那么不明白就不要乱说.
P:多项式时间可解决
NP:多项式时间 ...
cjaizss 发表于 2011-12-04 02:24

再加两条吧,扫扫盲,只是希望以后作无谓的挣扎少一点就行了.
PSPACE:多项式空间可解决,比如本题
PSPACE-C:类同NPC与NP的关系
EXPTIME:2^(p(n))时间可解决,p(n)多项式
已经证明P是NP子集,NP为PSPACE子集,PSPACE为EXPTIME子集
但以上是否是真子集.目前不知道,NP?=P只是其中一项而已.
但P的确是EXPTIME的真子集,这早已知道

再加个NPH,NP转化的问题,我忘记lz的问题是否也是NPH了,要证明,累了,不想了