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

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

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

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

f*g2010-07-11 07:07

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*Z2010-07-11 07:07

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*g2010-07-11 07:07

3 楼

好像partition problem是这个问题的一个子集,但只能说这个问题至少也是NPC级别,我再看看
optimization problems是什么。