首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

有点难的数组分割有关问题!

2012-02-05 
有点难的数组分割问题!!任意给出一个有N个数的数组A(N为偶数),请将该数组等分成两个字数组A1,A2;要求A1中

有点难的数组分割问题!!
任意给出一个有N个数的数组A(N为偶数),请将该数组等分成两个字数组A1,A2; 
要求A1中所有元素之和S1与A2中所有元素之和S2的差为最小?

[解决办法]
先把所有的数加起来除2得到M
然后题目变成从N中取N/2个数,
使其和最接近M
遍历就Ok了
[解决办法]
其实就是背包贪心的问题: 
使得得到的一组解的和最接近整个数组元素和的一半.
算出一半后直接贪心就可以得到结果.
[解决办法]
说一下思想:
1、求总数,算数组总数的一半half
2、将前一半看作A数组,后一半看做B数组
3、现在用迭代算法求A
4、如果某数组元素a未加入A,同时,用a替换A中某元素,能使A得总值更小,就替换
5、迭代结束得条件,循环一次后,A的总值没有变化,就结束

注:上面的代码本人已经测试过,没问题。

some bugs:
1、数组如果先排序,算法可以稍作改进,效率会更高
2、用作标记得数组可以直接和原数组合并成二维数组

热点排行