《编程珠玑》第二章习题:n元集合中最小的k元子集

《编程珠玑》第二章习题

给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集合，其元素之和不超过t？

 

O(n log k) 

Step 1.选取0..k-1元素填充数组r，用二分法插入。

Step 2.然后从k个元素开始，与结果中的元素比较，才用二分法插入.此时数组r共k+1个元素。去除r中最后一个元素。

Step 3.重复step 2直至结束。

 

算法复杂度：插入元素时，用二分法。其复杂度为log k. 共有n个元素， 其复杂度为O(n log k).

 

O(nk) 

若step 2中采取顺序插入，则其复杂度为O(nk);

 

用冒泡法排序，排k趟，其复杂度为O(nk);

 

 

这个二分法写的好烂啊。。无语。蠢死。

my @n;
my @r;
my $k = 5;
my $t = 10;
for(0..100){
    $n[$_] = int(rand(100));
}
print "input : @n \n";
print "--------------------------------------------\n";


for(0..$k-1){
    $r[$_] = 10000;
}


for my $cur (@n){

    my $start = 0;
    my $end = $k-1 ;
    my $tindex ;
    my $mid;

    while(1){
        $mid = int(($end+$start)/2);

        if($cur>=$r[$mid] and $cur<= $r[$mid+1])
        {
            $tindex = $mid + 1;
            last;
        }
        if($start+1 == $end){
            $tindex = $end;
            if($cur <= $r[$start]){
                $tindex = $start;
            }
            elsif($cur> $r[$end]){
                $tindex = $end +1;

            }
            last;
        }
        else{
            if($cur > $r[$mid+1]){
                $start = $mid;
            }
            elsif($cur < $r[$mid]){
                $end = $mid;
            }
        }
    }
    next if($tindex >=$k);
    for (my $i = $k -1 ; $i >= $tindex; $i--){
        $r[$i] = $r[$i-1];
    }
    $r[$tindex] = $cur;
}
my $sum;
for(@r){
    $sum += $_;
}
print "@r \n" if($sum<=$t);