C++-数组分组算法

C++-数组分组算法

灵芸 发布于 2017-09-28 字数 70 浏览 1667 回复 6

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

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

甜柠檬 2017-11-07 6 楼

这次看懂了,假设一个一组数据的和为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));  //第二组数
泛泛之交 2017-10-25 5 楼

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

灵芸 2017-10-18 4 楼

这个题目是典型的线性规划中的整数规划问题,形式化描述为:
假定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(动规)的方法解这个问题,本质上是一样。

甜柠檬 2017-10-13 3 楼

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

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

瑾兮 2017-10-02 2 楼

用perl实现的版本

 #!/usr/bin/perl

use strict;
use warnings;

use List::Util qw( sum );

my @numbers = generate_list();

print "@numbersnn";

my (@A, @B);
my $N = @numbers;

while ( @numbers ) {
my $n = pop @numbers;
printf "Step: %dn", $N - @numbers;
{
no warnings 'uninitialized';

if ( sum(@A) < sum(@B) ) {
push @A, $n;
}
else {
push @B, $n;
}
printf "A: %sntsum: %dntnum elements: %dn",
"@A", sum(@A), scalar @A;
printf "B: %sntsum: %dntnum elements: %dnn",
"@B", sum(@B), scalar @B;
}
}

sub generate_list { grep { rand > 0.8 } 1 .. 450 }

晚风撩人 2017-10-01 1 楼

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

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

ps: 我不会算法,哈哈