return on investment maximizer

t2q23.pl

#!/usr/bin/perl

use strict;
use warnings;

my $saving = 1187;
my $stocks = [39,16,124,172,110,273,245,261,43,231,97,162,217,59,240,157,179,207,227,235,24,8,126,153,232,81,267,150,202,92,44,122,127,176,171,113,82,209,263,266,14,120,291,155,84,199,223,66,265,121,63,37,52,215,44,134,262,92,138,227,151,231,108,202,284,42,148,125,146,289,14,137,27,206,172,120,134,169,104,249,34,185,262,295,174,262,42,175,235,185,26,69,199,49,45,126];
my $future = [16,252,240,226,243,1,242,55,297,49,240,86,299,238,121,282,228,0,234,267,133,277,61,51,269,79,25,26,268,282,232,250,232,293,118,298,290,261,238,257,297,27,50,200,16,247,244,28,294,259,117,298,229,278,152,229,182,168,58,245,291,10,36,275,258,143,194,250,244,281,269,274,25,294,263,26,291,252,225,196,299,275,276,98,54,289,18,298,199,220,269,13,256,293,187,45];

sub hack {
   my $res = 0;
   my $sa = $_[0];
   my @cv = @{$_[1]};
   my @fv = @{$_[2]};
   my $n = scalar(@cv);
   printf "cv: %s\n",join',',@cv;
   printf "scv: %s\n",join',',sort { $a <=> $b } @cv;
   printf "fv: %s\n",join',',@fv;
   my @gv = map { $fv[$_] - $cv[$_] } (0 .. $n-1);
   printf "gv: %s\n",join',',@gv;
   my @si = sort { $gv[$b]/$cv[$b] <=> $gv[$a]/$cv[$a] } (0 .. $n-1);
   printf "si: %s\n",join',',@si;
   my $remain = $sa;
   for my $i (@si) {
     printf "i:%02d sa: %4d, cv: %3d, fv: %3d gv: %3d ", $i,$remain,$cv[$i],$fv[$i],$gv[$i];
     if ($remain >= $cv[$i]) {
       if ($gv[$i] > 0) {
       $res += $gv[$i];
       $remain -= $cv[$i];
       }
     }
     printf "-> remain: %s; res: %s\n",$remain, $res;
   }
   return $res < 0 ? 0 : $res;
}

my $result = &hack($saving,$stocks,$future);

print "$result\n"; # response 4330 ! (not 4236)