Advertisement
pongfactory

update 20May2016

May 20th, 2016
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
MatLab 5.92 KB | None | 0 0
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%%%%%%%%%%%% One-dimensional bin packing problem %%%%%%%%%%%%%%%%%%%%
  3. %%%%%%%%%%%%%%%%%%% Project II | 20 May 2016%%%%%%%%%%%%%%%%%%%%%%%%%  
  4. %%%%%%%%%%%%%%%% WANCHAI SUKSRINUAN & AMNUY kUYBAN %%%%%%%%%%%%%%%%%%%
  5. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  6.  
  7. clc;
  8. clear;
  9. disp('................................................');
  10. disp('One dimensional bin-packing heuristic algorithms');
  11. disp('Select Input Type');
  12. %disp('Press 1 - Auto Input;');
  13. %disp('Press 1 - Manual Input;');
  14.  
  15.  
  16. %chosen=input('Enter your choice : ');
  17. % if chosen==1,
  18. % %u = [5 3 4 9 1 8 7 8 11 5];
  19. % %u = [4 11 8 5 2 8 7 2 2 11];
  20. % r_keyboard = input('Number of object : ');
  21. % number_object = r_keyboard;
  22. % u = round(rand(1,number_object)*10)+1;
  23. % %round(rand(1)*100);
  24. %     for i=1:number_object,
  25. %        
  26. %         fprintf('object %d', i);
  27. %         fprintf(' = %d\n', u(i));
  28. %     end
  29. %     %sort(u)
  30. % input_input = u
  31. % b = sort(u, 'descend');
  32. % u = b
  33. %
  34. % end
  35.  
  36.  
  37. r_keyboard = input('Number of object : ');
  38. %u = [5 3 4 9 1 8 7 8 11 5];
  39. number_object = r_keyboard;
  40. start = 1;
  41.     for i=1:number_object,
  42.         fprintf('object %d', i);
  43.         u(i) = input(' Insert your object value : ');
  44.         fprintf('object %d', i);
  45.         fprintf(' = %d\n', u(i));
  46.        
  47.         fprintf('copy object %d', i);
  48.         copy(i) = input(' Insert your copy object value : ');
  49.         fprintf('copy %d', i);
  50.         fprintf(' = %d\n', copy(i));
  51.        
  52.         for j=start:(start+copy(i)-1),
  53.             input_all(j) = u(i);
  54.         end
  55.         start = start+copy(i);
  56.    
  57.     input_all
  58.    % input_input = u
  59.     u = input_all; %input
  60.     b = sort(u, 'descend');
  61.     u = b
  62.  
  63.  
  64. end
  65.  
  66. %u = [1 4 2 1 2 3 5 5 6 3 2 4];  
  67. n = length(u);
  68.  
  69. %fprintf('BIN = %d', i);
  70. C = input(' Insert your BIN value : ');
  71. %fprintf('bin size = %d\n', C);
  72. disp('................................................');
  73. r = C*ones(1,n);
  74. w = zeros(n);
  75.  
  76. [ud1,idec]=sort(-u); % sort obj.
  77. ud=-ud1;
  78. [tmp,irec]=sort(idec);
  79.  
  80. disp('................................................');
  81. disp('One dimensional bin-packing heuristic algorithms');
  82. disp('Press 0 - default choice;');
  83. disp('Press 1 - FFD method;');
  84. %disp('Press 2 - first fit decreasing method;');
  85. disp('Press 2 - BFD method;');
  86. %disp('Press 4 - best fit decreasing method;');
  87. chosen=input('Enter your choice : ');
  88.  
  89.  
  90.  
  91.  
  92. % ****************************  FFD method  ****************************** %
  93. if chosen==0 | chosen==1,  % first fit method
  94. wff=w; rff=r+0.01; % initialize for first fit method
  95. for i=1:n,
  96.    idx=min(find([u(i)*ones(1,n)<=rff]));
  97.    wff(i,idx)=1;
  98.    rff(idx)=rff(idx)-u(i);  % update the state
  99. end
  100. disp('% *******************************');
  101. disp('the assignment are:')
  102. disp(wff)
  103.  
  104. % B = wff(:,1)
  105. % A = input_input'
  106. % B = logical(B);
  107. % A(B)
  108.  
  109. N_feature = size(wff,2);
  110.  
  111. input_temp = [u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u'];
  112. % Q = [input_temp(:,1:4)]
  113. % C = wff(:,1:4);
  114. % C = logical(C);
  115. % Q(C)
  116. %show_out = input_temp(C)
  117.  
  118. for k=1:N_feature,
  119.     fprintf('Data in Bin %d', k);
  120.     B = wff(:,k);
  121.     %A = input_input';
  122.     A = input_temp(:,k);
  123.     B = logical(B);
  124.     output_ans = A(B)
  125.    
  126.    % output_ans(k) = A(B);
  127. end
  128.  
  129.  
  130. disp('First fit (FFD) method: ')
  131. occpff=u*wff;
  132. disp(['Total # of bins used = ' int2str(sum([occpff > 0]))]);
  133. nbinff=sum([occpff > 0]);
  134. disp('the occupancy of each bin after packing are:');
  135. disp(occpff(1:nbinff))
  136. end
  137. % ******************************************************************************* %
  138.  
  139.  
  140.  
  141.  
  142. % ****************************   BFD method  ****************************** %
  143. if chosen==0 | chosen==2,  % first fit method
  144. wbf=w; rbf=r; % initialize for best fit method
  145. for i=1:n,
  146.    % disp(['u(' int2str(i) ') = ' int2str(u(i))]);
  147.    % disp('r = '); disp(r);
  148.    idx1=find([u(i)*ones(1,n) <= rbf]); % indices of bins still have spaces left
  149.    [tmp,idx2]=min(rbf(idx1)-u(i));    % find the index within idx1 that best fits u(i)
  150.    wbf(i,idx1(idx2))=1; rbf(idx1(idx2))=tmp; % update the state
  151.    % disp('Press any key to continue ...'); pause
  152. end
  153. %wbf=wbf(irec,:); ; % sort it back to the original assignment order
  154. %disp('% *******************************');
  155. %disp('First fit decreasing (FFD) method: ')
  156. disp('Best fit decreasing (BFD) method: ')
  157. disp('the assignment are:')
  158. disp(wbf)
  159.  
  160. N_feature = size(wbf,2);
  161.  
  162. input_temp = [u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u' u'];
  163. % Q = [input_temp(:,1:4)]
  164. % C = wff(:,1:4);
  165. % C = logical(C);
  166. % Q(C)
  167. %show_out = input_temp(C)
  168.  
  169. for k=1:N_feature,
  170.     fprintf('Data in Bin %d', k);
  171.     B = wbf(:,k);
  172.     %A = input_input';
  173.     A = input_temp(:,k);
  174.     B = logical(B);
  175.     output_ans = A(B)
  176.    
  177.    % output_ans(k) = A(B);
  178. end
  179.  
  180.  
  181. disp('% *******************************');
  182. disp('Best fit (BF) method: ')
  183. % disp('the assignment are:')
  184. % disp(wbf)
  185. occpbf=u*wbf;
  186. nbinbf=sum([occpbf > 0]);
  187. disp(['Total # of bins used = ' int2str(nbinbf)]);
  188. disp('the occupancy of each bin after packing are:');
  189. disp(occpbf(1:nbinbf))
  190.  
  191. % occpffd=u*wffd;
  192. % nbinffd=sum([occpffd > 0]);
  193. % disp(['Total # of bins used = ' int2str(nbinffd)]);
  194. % disp('the occupancy of each bin after packing are:');
  195. % disp(occpffd(1:nbinffd))
  196. % %disp(idx)
  197. % % disp('Press any key to continue to Best fit method ...'); pause
  198.    
  199. end
  200. % ******************************************************************************* %
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement