首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >将一组人分成两个不相交的子组(任意大小),并找到一些值

问将一组人分成两个不相交的子组(任意大小),并找到一些值
EN

Stack Overflow用户
提问于 2013-12-17 00:46:51
回答 1查看 728关注 0票数 0

正如我们从编程中了解到的,有时问题中的微小变化会显著改变其解决方案的形式。

首先,我想创建一个解决以下问题的简单算法,并使用bigtheta表示法对其进行分类:

将一组人分成两个不相交的子组(任意大小),这样两个子组成员的总年龄差异就越大。

现在,我需要改变问题,以便期望的差别尽可能小,并对我的方法进行分类。

,首先,我需要创建初始算法。为此,我应该进行某种排序,以便将团队分开,我应该如何继续呢?

编辑:对于第一个问题,我们已经排除了一个集是一个空集的可能性。所以我们所要做的就是线性搜索,找到最小年龄,然后把它放在一个集合中。SetA现在有了所有其他的年龄,除了setB的年龄,也就是最小年龄。这是这两组年龄的最大差异,尽可能高。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-12-17 01:32:16

按照您描述第一个问题的方式,它只要求您找到最小元素(如果子组至少包含一个成员),这是很简单的,否则它已经解决了。

第二个问题可以递归地解决--伪代码是:

代码语言:javascript
复制
// 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,从而添加一个测试条件来停止分支,但是这种想法保持不变。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/20623869

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档