首页 > 试题广场 >

数组中的数分为两组，让给出一个算法，使得两个组的和的差的绝对

[问答题]
数组中的数分为两组，让给出一个算法，使得两个组的和的差的绝对值最小，数组中的数的取值范围是0<x<100，元素个数也是大于0， 小于100 。
比如a[]={2,4,5,6,7},得出的两组数｛2，4，6｝和｛5，7｝，abs(sum(a1)-sum(a2))=0；
比如｛2，5，6，10｝，abs（sum(2,10)-sum(5,6))=1,所以得出的两组数分别为｛2，10｝和｛5，6｝。  <x><100，元素个数也是大于0， 小于100="" 。比如a[]="{2,4,5,6,7},得出的两组数｛2，4，6｝和｛5，7｝，abs(sum(a1)-sum(a2))=0；" 比如｛2，5，6，10｝，abs（sum(2,10)-sum(5,6))="1,所以得出的两组数分别为｛2，10｝和｛5，6｝。</x>
添加回答
ewewew头像 ewewew
背包问题的变化方式。参考http://www.tuicool.com/articles/ZF73Af
发表于 2016-04-07 16:42:03 回复(0)
小酒窝头像 小酒窝
首先把数组a的所有元素求和sum, 然后取和的一半设为x,然后遍历数组a的所有子集并且分别求出所有子集的元素之和sum(i);比较abs(x-sum(i)),取小。
发表于 2015-04-22 16:03:41 回复(0)
土豆先生头像 土豆先生
没有时间限制的话，可以用回溯法遍历解空间，解空间是子集树。
但给定了数据的取值范围，是不是有什么更好的解法
编辑于 2015-04-18 17:46:17 回复(0)
提交观点

问题信息

复杂度 盛趣游戏
上传者：Mr.Sky
难度：
3条回答 26477浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号