数组平分问题
时间：2011-07-13
来源：互联网
给定一个大小为N的数组，N为偶数，从中找出N/2个数使这N/2个数的和最接近剩余的N/2个数的和。例如：给定数组：
{2,3,5,1,8,6}，结果为：2，3，8与1，5，6。此题是否有最优算法？
{2,3,5,1,8,6}，结果为：2，3，8与1，5，6。此题是否有最优算法？
作者: nkorange 发布时间: 2011-07-13
我想了一个比较暴力的方法：用类似0-1背包的方法来做。这个可以转换一个角度看，设N个数的总和为SUM，那么现在的目的就是从N个数中选出N/2个数来填SUM/2的包，使这个包尽量的满。普通的0/1背包只需要一个1维数组就可以了，而这里可以用一个2维数组来做，增加的一维用来记录包里现在有多少个石子。
我对这个问题也很好奇，高手快点出来吧。。。
我对这个问题也很好奇，高手快点出来吧。。。
作者: onlyg 发布时间: 2011-07-13
这样的话，复杂度应该是：N×（N/2）×（SUM/2）即：当前最大编号×当前选择的数目×当前达到的和。不知我分析的正确吗？
引用 1 楼 onlyg 的回复:
我想了一个比较暴力的方法：用类似0-1背包的方法来做。这个可以转换一个角度看，设N个数的总和为SUM，那么现在的目的就是从N个数中选出N/2个数来填SUM/2的包，使这个包尽量的满。普通的0/1背包只需要一个1维数组就可以了，而这里可以用一个2维数组来做，增加的一维用来记录包里现在有多少个石子。
我对这个问题也很好奇，高手快点出来吧。。。
我想了一个比较暴力的方法：用类似0-1背包的方法来做。这个可以转换一个角度看，设N个数的总和为SUM，那么现在的目的就是从N个数中选出N/2个数来填SUM/2的包，使这个包尽量的满。普通的0/1背包只需要一个1维数组就可以了，而这里可以用一个2维数组来做，增加的一维用来记录包里现在有多少个石子。
我对这个问题也很好奇，高手快点出来吧。。。
作者: nkorange 发布时间: 2011-07-13
是的啊
作者: onlyg 发布时间: 2011-07-13
微软技术面试心得上不是有这题么？
作者: yaoweijq 发布时间: 2011-07-13
没有看过那个啊，求教。
引用 4 楼 yaoweijq 的回复:
微软技术面试心得上不是有这题么？
微软技术面试心得上不是有这题么？
作者: nkorange 发布时间: 2011-07-13
昨天我也发了这个贴，一起讨论吧
http://topic.csdn.net/u/20110712/15/1b4021c9-5bc2-447f-afef-58df71325e78.html?39508
http://topic.csdn.net/u/20110712/15/1b4021c9-5bc2-447f-afef-58df71325e78.html?39508
作者: babykick 发布时间: 2011-07-13
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读：74
-
如何安装mysql8.0
阅读：31
-
Word快速设置标题样式步骤详解
阅读：28
-
20+道必知必会的Vue面试题（附答案解析）
阅读：37
-
HTML如何制作表单
阅读：22
-
百词斩可以改天数吗？当然可以，4个步骤轻松修改天数！
阅读：31
-
ET文件格式和XLS格式文件之间如何转化？
阅读：24
-
react和vue的区别及优缺点是什么
阅读：121
-
支付宝人脸识别如何关闭?
阅读：21
-
腾讯微云怎么修改照片或视频备份路径?
阅读：28
