Finish 1998-12-21 00:00:00 UTC

cumsum&exchange 8

by Hakan Erdogan

Status: Passed
Results: 0.88% blank
CPU Time: 7.962
Score: 210.462
Submitted at: 1998-12-18 15:32:38 UTC
Scored at: 2000-03-16 16:51:51 UTC

Current Rank: 442nd
Based on: cumsum&exchange 7 (diff)
Basis for: cumsum&exchange 9 (diff)

Comments
Please login or create a profile.
Code
function [indexList,gap,time]= binpack(songList,mediaLength)
% combination of cdknow and sequential exchanges
%
[s,is] = sort(songList);
tso = length(s);
goal=0.08/max(20,tso)*mediaLength;
ts = min(tso,round(4*tso*mediaLength/sum(s)));
N = round(30+0.1*tso);
[d,so] = sort(rand(ts,N));
r = floor((0.25*(tso-ts))*rand(1,N));
so = so+r(ones(1,ts),:);
order=is(so);
val=songList(order);
cs = cumsum(val);
chosen=cs<=mediaLength;

ss=sum(chosen);
val(chosen)=-val(chosen);
gap = mediaLength-cs(ss+(0:ts:ts*N-ts));

inc=0:ts:ts*N-ts;
ndo=min(3,ts);
k=1;
while(min(gap)> goal & k <= ndo)
        temp=val+val(k*ones(1,ts),:);
        temp(k,:)=val(k,:);
        [mt imt]=max(temp.*(temp+1e-10<=gap(ones(1,ts),:)));
        indic = -(mt>0);
        indic(~indic)=1;
        val([k+inc imt+inc])=[indic indic].*val([k+inc imt+inc]);
        gap=gap-max(0,mt);
        k=k+1;
end
[gap igap]=min(gap);
border=order(:,igap);
indexList=border(find(val(:,igap)<0))';