求一个构造算法

欢迎您:游客帮助

求一个构造算法

加为好友

发表于：2008-08-19 15:26:35 楼主

一个数的集合A定义它的一个函数
f(A) = a1-a2+a3-a4+a5-a6+……
这里a1是A中最大的数,a2是A中第二大的数,依次类推
已知若干个集合A1,A2,……,An现在要在每个Ai中选出一个数组成新的集合A
请问：
一：如何构造A使得f(A)最小
二：如何构造A使得f(A)最大

问题点数：200 回复次数：2 修改删除举报引用回复

发表于：2008-08-19 17:42:501楼得分:0

好像挺麻烦的，不太容易有很高效的算法。
n个集合，假设每个集合都有m个元素，我能想到的是复杂度为O(m^2*n^2*2^n)的动态规划，已经超过指数级了。

发表于：2008-09-01 11:26:552楼得分:0

F(a)=a1+a3+a5+...-（a2+a4+a6+...);
F（a)=G(a)-H(a),因为G(a) H(a)均为单调增函数
所以,取A1,A2,……,An最小数序列,与最大数序列可得到F(a)的最大与最小值.
因为单调,则用贪心算法即可