把已知的n个整数分成两组,求使两组数据各自的和相差最小的分组方法

2010-12-26 10:18:20

6 Answers

还要考虑排列的问题啊。A(n,n)种排列,都要进行一次加和,然后按照上边的程序比较。然后整个计算量会很大,时间复杂度会是A(n,n)*2n,随着数量增加阶乘式上升。

2010-12-26 12:39:56

这次看懂了,假设一个一组数据的和为h1,另外一组数据的和为h2,所有数据的和为total,则
h1 + h2 = total;
则h2 = total - h1;
而题目要求的是|h1-h2|,则
|h1-h2| = |h1-(total - h1)| = |2*h1 - total|;
既两倍h1减去所有数的总和,因此如果使用程序来实现,循环二遍,求出每一步的和及总的和就行。拿php写了一个,时间复杂度是2n的

$a = array(1,2,3,-4,5,6); $b = array(); $tt = 0; foreach($a as $v) { $tt += $v; $b[] = 2*$tt; } $cc = $index = 0; $min = $tt; foreach($b as $kk=>$vv) { //找出最小的差值 $cc = abs($vv-$tt); if($cc < $min){ $min = $cc; $index = $kk; } } var_dump(array_slice($a,0,$index+1));//第一个组数 var_dump(array_slice($a,$index+1));//第二组数

2010-12-26 14:18:43

动规?
先求出两组数的平均值.然后不停的重试.

要么直接把数分为二组,然后不停的找出差值(A1),然后再在二个数组中找差值小于A1的,并交换?

ps: 我不会算法,哈哈

2010-12-26 15:43:45

思路:1.将这些数据先按从大到小的顺序排到数组s里。
2.声明两个数组s1、s2,将s第一个数据放入s1,第二个放入s2,比较两个数组之和,将s第三个数据放入到s1、s2之和小的那一数组中。以此类推。
3.s1、s2即所需的数据。

————这位同学的算法显然不严谨,比如3,4,6,7,8,按照你的算法就是13,15,然而实际差最小的是14,14。实际上,这题除了遍历之外没有更好的方法。

2010-12-26 17:08:12

这个题目是典型的线性规划中的整数规划问题,形式化描述为:
假定n个数分别为a1,a2,...an, 他们的和记为T。
定义函数

f(x1, x2, ... xn)=a1x1 + a2x2 + ... + anxn (其中 xi = 0 or 1).

求使得函数sqr(f(x1, x2, ... xn) - T/2)达到最小值的整数解。
在数学计算工具包中,如Matlab,有线性规划的计算工具,大家也可以参照分值界定法的算法。内容比较多就不在这里啰嗦了。小齐的说法也是对的,也可以用Dynamic Programming(动规)的方法解这个问题,本质上是一样。

2010-12-26 18:33:55

用perl实现的版本

#!/usr/bin/perl use strict; use warnings; use List::Util qw( sum ); my @numbers = generate_list(); print "@numbers\n\n"; my (@A, @B); my $N = @numbers; while ( @numbers ) { my $n = pop @numbers; printf "Step: %d\n", $N - @numbers; { no warnings 'uninitialized'; if ( sum(@A) < sum(@B) ) { push @A, $n; } else { push @B, $n; } printf "A: %s\n\tsum: %d\n\tnum elements: %d\n", "@A", sum(@A), scalar @A; printf "B: %s\n\tsum: %d\n\tnum elements: %d\n\n", "@B", sum(@B), scalar @B; } } sub generate_list { grep { rand > 0.8 } 1 .. 450 }

2010-12-26 19:50:17
您不能回答该问题或者回答已经关闭!

相关文章推荐

  • C#中using指令的几种用法

    using + 命名空间名字,这样可以在程序中直接用命令空间中的类型,而不必指定类型的详细命名空间,类似于Java的import,这个功能也是最常用的,几乎每个cs的程序都会用到

  • C#实例解析适配器设计模式

    将一个类的接口变成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够一起工作

  • C#开发高性能Log Help类设计开发

    项目中要在操作数据库的异常处理中加入写Log日志,对于商业上有要求,写log时对其它操作尽可能影响小,不能因为加入log导致耗时太多

  • C#运行时相互关系

    C#运行时相互关系,包括运行时类型、对象、线程栈和托管堆之间的相互关系,静态方法、实例方法和虚方法的区别等等

  • C#基础概念之延迟加载

    延迟加载(lazy load)是Hibernate3关联关系对象默认的加载方式,延迟加载机制是为了避免一些无谓的性能开销而提出来的,所谓延迟加载就是当在真正需要数据的时候,才真正执行数据加载操作

  • C#开发中的反射机制

    反射的定义:审查元数据并收集关于它的类型信息的能力。元数据(编译以后的最基本数据单元)就是一大堆的表,当编译程序集或者模块时,编译器会创建一个类定义表,一个字段定义表,和一个方法定义表等

  • 使用托管C++粘合C#和C++代码(二)

    本文实现一下C++代码调用C#代码的过程。我构造一个简单并且直观的例子:通过C++ UI 触发C# UI.

  • C#协变和逆变

    “协变”是指能够使用与原始指定的派生类型相比,派生程度更大的类型,“逆变”则是指能够使用派生程度更小的类型

  • Async和Await使异步编程更简单

    C#5.0中async和await两个关键字,这两个关键字简化了异步编程,之所以简化了,还是因为编译器给我们做了更多的工作

  • C#中的索引器的简单理解和用法

    C#中的类成员可以是任意类型,包括数组和集合。当一个类包含了数组和集合成员时,索引器将大大简化对数组或集合成员的存取操作

  • 使用托管C++粘合C#和C++代码(一)

    C#在xml读写,数据库操纵,界面构造等很多方面性能卓越;C++的效率高,是底层开发的必备武器

  • 深入C# 序列化(Serialize)、反序列化(Deserialize)

    C#中的序列化和反序列化,序列化是.NET运行时环境用来支持用户定义类型的流化的机制