MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 再问数组瓜分, 这种简单解法是否正确

再问数组瓜分, 这种简单解法是否正确

www.MyException.Cn  网友分享于:2013-04-23  浏览:4次
再问数组分割, 这种简单解法是否正确
本帖最后由 youyou1912 于 2013-04-21 17:42:46 编辑
一个2n的整数数组,分成n元素两组,保证两组和之差的绝对值最小
设计算法,保证两组和之差的绝对值最小。

编程之美上的一题. 解法说的也很清楚. 动态规划解法, 复杂度为 O(N^2 * SUM) 
也有人提了新思路
http://blog.sina.com.cn/s/blog_66223402010164ux.html

我也有一个很简单的思路, 不晓得是否正确. 
时间复杂度只有O(N*LogN), 空间O(N)

思路就是
假设: 全部数字>=0.
1. 降序排序
2. 两个子数组A,B, 开始遍历排序好的数组, 两个数组的和, 谁小就分配给谁,
3. 一直分配到结束或者其中一个数组个数为n为止.
4. 如果一个数组个数到n, 则剩下的都属于另外一个数组.

举例:
101,88,87,10,9,8,1,1,1,1   (2n=10, n=5)
1. A: {101}, SumA=101, B={88}, SumB=88  (101->A, 88->B)
2. A: {101}, SumA=101, B={88, 87}, SumB=175  (SumA>SumB, 87->B)
3. A: {101,10}, SumA=111, B={88, 87}, SumB=175  (SumA<SumB, 10->B)
.......
5. A: {101, 10, 9, 8, 1}, B:{88, 87}
6. A: {101, 10, 9, 8, 1} SumA=129, B:{88, 87, 1,1,1}, SumB=178, Delta=49

时间复杂: 排序O(N*LogN)+遍历分配O(N)

以上算法基于所有数字>=0, 如果有负数, 可以预处理都+最小负数的绝对值来改为正数, 思路一样.
请教各位, 以上算法是否正确?
算法 编程之美 数组分割

------解决方案--------------------
只要近似的话还可以凑数。最优的话肯定不对
100 80 80 60 41 1

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有