Project II - One Bin (New)(9 April 2016)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%% One-dimensional bin packing problem %%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%% Project II | 9 April 2016%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% WANCHAI SUKSRINUAN & AMNUY kUYBAN %%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

clc;
clear;
disp('................................................');
disp('One dimensional bin-packing heuristic algorithms');
disp('Select Input Type');
disp('Press 1 - Auto Input;');
disp('Press 2 - Manual Input;');


chosen=input('Enter your choice : ');
if chosen==1,
%u = [5 3 4 9 1 8 7 8 11 5];
%u = [4 11 8 5 2 8 7 2 2 11];
r_keyboard = input('Number of object : ');
number_object = r_keyboard;
u = round(rand(1,number_object)*10)+1;
%round(rand(1)*100);
    for i=1:number_object,

        fprintf('object %d', i);
        fprintf(' = %d\n', u(i));
    end
end

if chosen==2,
r_keyboard = input('Number of object : ');
%u = [5 3 4 9 1 8 7 8 11 5];
number_object = r_keyboard;

    for i=1:number_object,
        fprintf('object %d', i);
         u(i) = input(' Insert your object value : ');
        fprintf('object %d', i);
        fprintf(' = %d\n', u(i));
    end
end

%u = [1 4 2 1 2 3 5 5 6 3 2 4];
n = length(u);
C = 20;
fprintf('bin size = %d\n', C);
disp('................................................');
r = C*ones(1,n);
w = zeros(n);

[ud1,idec]=sort(-u); % sort obj.
ud=-ud1;
[tmp,irec]=sort(idec);

disp('................................................');
disp('One dimensional bin-packing heuristic algorithms');
disp('Press 0 - default choice;');
disp('Press 1 - first fit method;');
disp('Press 2 - best fit method;');
disp('Press 3 - first fit decreasing method;');
disp('Press 4 - best fit decreasing method;');
chosen=input('Enter your choice : ');




% ****************************  First fit method  ****************************** %
if chosen==0 | chosen==1,  % first fit method
wff=w; rff=r; % initialize for first fit method
for i=1:n,
   idx=min(find([u(i)*ones(1,n)<=rff]));
   wff(i,idx)=1;
   rff(idx)=rff(idx)-u(i);  % update the state
end
disp('% *******************************');
disp('the assignment are:')
disp(wff)
disp('First fit (FF) method: ')
occpff=u*wff;
nbinff=sum([occpff > 0]);
disp('the occupancy of each bin after packing are:');
disp(occpff(1:nbinff))
end
% ******************************************************************************* %







% ****************************   Best fit method  ****************************** %
if chosen==0 | chosen==2,  % first fit method
wbf=w; rbf=r; % initialize for best fit method
for i=1:n,
   idx1=find([u(i)*ones(1,n) <= rbf]);
   [tmp,idx2]=min(rbf(idx1)-u(i));
   wbf(i,idx1(idx2))=1; rbf(idx1(idx2))=tmp; % update the state
end
disp('% *******************************');
disp('the assignment are:')
disp(wbf)
disp('Best fit (BF) method: ')
occpbf=u*wbf;
nbinbf=sum([occpbf > 0]);
disp('the occupancy of each bin after packing are:');
disp(occpbf(1:nbinbf))
end
% ******************************************************************************* %








% ******************   first fit decreasing methodt method  ********************* %
if chosen==0 | chosen==3,  % first fit method
wffd=w; rffd=r; % initialize for first fit method
for i=1:n,
   % disp(['ud(' int2str(i) ') = ' int2str(ud(i))]);
   % disp('r = '); disp(rffd);
   idx=min(find([ud(i)*ones(1,n)<=rffd]));
   % disp(['u(' int2str(i) ') is assigned to b(' int2str(idx) ');']);
   wffd(i,idx)=1; rffd(idx)=rffd(idx)-ud(i);  % update the state
end
wffd=wffd(irec,:); % sort it back to the original assignment order
%disp('% *******************************');
%disp('First fit decreasing (FFD) method: ')
disp('the assignment are:')
disp(wffd)
occpffd=u*wffd;
nbinffd=sum([occpffd > 0]);
disp(['Total # of bins used = ' int2str(nbinffd)]);
disp('the occupancy of each bin after packing are:');
disp(occpffd(1:nbinffd))
%disp(idx)
% disp('Press any key to continue to Best fit method ...'); pause

end
% ******************************************************************************* %







% *******************   Best fit decreasing method  ****************************** %
if chosen==0 | chosen==4,
wbfd=w; rbfd=r; % initialize for best fit method
    for i=1:n,

       idx1=find([ud(i)*ones(1,n) <= rbfd]);
       [tmp,idx2]=min(rbfd(idx1)-ud(i));
       wbfd(i,idx1(idx2))=1; rbfd(idx1(idx2))=tmp; % update the state

    end
wbfd=wbfd(irec,:);
disp('% *******************************');
disp('the assignment are:')
disp(wbdf)
disp('Best fit decreasing (BFD) method: ')
occpbfd=u*wbfd;
nbinbfd=sum([occpbfd > 0]);
disp(['Total # of bins used = ' int2str(nbinbfd)]);
disp('the occupancy of each bin after packing are:');
disp(occpbfd(1:nbinbfd))

end %
% ******************************************************************************* %