正如我们从编程中了解到的,有时问题中的微小变化会显著改变其解决方案的形式。
首先,我想创建一个解决以下问题的简单算法,并使用bigtheta表示法对其进行分类:
将一组人分成两个不相交的子组(任意大小),这样两个子组成员的总年龄差异就越大。
现在,我需要改变问题,以便期望的差别尽可能小,并对我的方法进行分类。
,首先,我需要创建初始算法。为此,我应该进行某种排序,以便将团队分开,我应该如何继续呢?
编辑:对于第一个问题,我们已经排除了一个集是一个空集的可能性。所以我们所要做的就是线性搜索,找到最小年龄,然后把它放在一个集合中。SetA现在有了所有其他的年龄,除了setB的年龄,也就是最小年龄。这是这两组年龄的最大差异,尽可能高。
发布于 2013-12-17 01:32:16
按照您描述第一个问题的方式,它只要求您找到最小元素(如果子组至少包含一个成员),这是很简单的,否则它已经解决了。
第二个问题可以递归地解决--伪代码是:
// compute sum of all elem of array and store them in sum
min = sum;
globalVec = baseVec;
fun generate(baseVec, generatedVec, position, total)
if (abs(sum - 2*total) < min){ // check if the distribution is better
min = abs(sum - 2*total);
globalVec = generatedVec;
}
if (position >= baseVec.length()) return;
else{
// either consider elem at position in first group:
generate(baseVec,generatedVec.pushback(baseVec[position]), position + 1, total+baseVec[position]);
// or consider elem at position is second group:
generate(baseVec,generatedVec, position + 1, total);
}现在只需用generate(baseVec,"",0,0)启动函数,其中""代表一个空向量。
通过将其应用到排序数组中,可以大大改进algo,从而添加一个测试条件来停止分支,但是这种想法保持不变。
https://stackoverflow.com/questions/20623869
复制相似问题