突然想到一个问题，分割一个set(包含整数)成2个sets，使得他们的sum的差最小 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 突然想到一个问题，分割一个set(包含整数)成2个sets，使得他们的sum的差最小

相关主题
● 请教算法：三等分石子 (转载)	● 问个算法体
● 请教一道算法题	● please help 这个题 (转载)
● 子集和问题和0-1背包问题的疑惑	● 关于面试的建议之一
● 程序员面试宝典	● three eggs 关于3个蛋的问题
● 给定一个数组，找出3个数乘积最大。	● 请教一个问题？
● 问最小窗口覆盖的面试题	● 再问一个IBM的题
● 这个题怎么做？	● 问一个给定的array 和一个sum value,找最小sub-array,谢谢
● 问道面试题：一堆数中找最大的100个	● 一道MS面试题

相关话题的讨论汇总
话题: npc话题: sets话题: sum话题: 最小话题: 使得

进入JobHunting版参与讨论

1

(共1页)

f*****g 发帖数: 309	1 看到这个题 http://discuss.techinterview.org/default.asp?interview.11.637605.9 一个set S包含很多整数，如何才能把它分割成2个sets， S1和S2，使得这2个sets里面数的sum的差最小。里面有人回帖说这个也是NPC。 partition problem是NPC，但是这个使得2个分割的sets的sum的差最小的问题还是NPC 吗？刚开始认为很容易，但是仔细一想，发现不好证明。请大家指教。
Z*****Z 发帖数: 723	2 http://en.wikipedia.org/wiki/Partition_problem NPC 【在 f*****g 的大作中提到】 : 看到这个题 : http://discuss.techinterview.org/default.asp?interview.11.637605.9 : 一个set S包含很多整数，如何才能把它分割成2个sets， S1和S2，使得这2个sets里面 : 数的sum的 : 差最小。里面有人回帖说这个也是NPC。 : partition problem是NPC，但是这个使得2个分割的sets的sum的差最小的问题还是NPC : 吗？刚开 : 始认为很容易，但是仔细一想，发现不好证明。 : 请大家指教。
f*****g 发帖数: 309	3 好像partition problem是这个问题的一个子集,但只能说这个问题至少也是NPC级别,我再看看 optimization problems是什么。

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 一道MS面试题	● 给定一个数组，找出3个数乘积最大。
● 一个面题	● 问最小窗口覆盖的面试题
● k-th smallest element - 最小的 k = 0 还是 k = 1?	● 这个题怎么做？
● a CS question	● 问道面试题：一堆数中找最大的100个
● 请教算法：三等分石子 (转载)	● 问个算法体
● 请教一道算法题	● please help 这个题 (转载)
● 子集和问题和0-1背包问题的疑惑	● 关于面试的建议之一
● 程序员面试宝典	● three eggs 关于3个蛋的问题

相关话题的讨论汇总
话题: npc话题: sets话题: sum话题: 最小话题: 使得

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)