pongfactory

[Decreasing] Prject II | Bin Packing 1D [FULL CODE]

May 1st, 2016
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
MatLab 7.38 KB | None | 0 0
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%%%%%%%%%%%% One-dimensional bin packing problem %%%%%%%%%%%%%%%%%%%%
  3. %%%%%%%%%%%%%%%%%%% Project II | 1 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 - first fit method;');
  84. disp('Press 2 - first fit decreasing method;');
  85. disp('Press 3 - best fit method;');
  86. disp('Press 4 - best fit decreasing method;');
  87. chosen=input('Enter your choice : ');
  88.  
  89.  
  90.  
  91.  
  92. % ****************************  First fit method  ****************************** %
  93. if chosen==0 | chosen==1,  % first fit method
  94. wff=w; rff=r; % 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'];
  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 (FF) method: ')
  131. occpff=u*wff;
  132. nbinff=sum([occpff > 0]);
  133. disp('the occupancy of each bin after packing are:');
  134. disp(occpff(1:nbinff))
  135. end
  136. % ******************************************************************************* %
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144. % ******************   first fit decreasing methodt method  ********************* %
  145. if chosen==0 | chosen==2,  % first fit method
  146. wff=w; rff=r; % initialize for first fit method
  147. for i=1:n,
  148.    idx=min(find([u(i)*ones(1,n)<=rff]));
  149.    wff(i,idx)=1;
  150.    rff(idx)=rff(idx)-u(i);  % update the state
  151. end
  152. disp('% *******************************');
  153. disp('the assignment are:')
  154. disp(wff)
  155.  
  156. N_feature = size(wff,2);
  157.  
  158.  input_temp = [u' u' u' u' u' u' u' u' u' u'];
  159. % Q = [input_temp(:,1:4)]
  160. % C = wff(:,1:4);
  161. % C = logical(C);
  162. % Q(C)
  163. %show_out = input_temp(C)
  164.  
  165. for k=1:N_feature,
  166.     fprintf('Data in Bin %d', k);
  167.     B = wff(:,k);
  168.     %A = input_input';
  169.     A = input_temp(:,k);
  170.     B = logical(B);
  171.     output_ans = A(B)
  172.    
  173.    % output_ans(k) = A(B);
  174. end
  175.  
  176.  
  177. disp('First fit (FF) method: ')
  178. occpff=u*wff;
  179. nbinff=sum([occpff > 0]);
  180. disp('the occupancy of each bin after packing are:');
  181. disp(occpff(1:nbinff))
  182. end
  183. % ******************************************************************************* %
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192. % ****************************   Best fit method  ****************************** %
  193. if chosen==0 | chosen==3,  % first fit method
  194. wffd=w; rffd=r; % initialize for first fit method
  195. for i=1:n,
  196.    % disp(['ud(' int2str(i) ') = ' int2str(ud(i))]);
  197.    % disp('r = '); disp(rffd);
  198.    idx=min(find([ud(i)*ones(1,n)<=rffd]));
  199.    % disp(['u(' int2str(i) ') is assigned to b(' int2str(idx) ');']);
  200.    wffd(i,idx)=1; rffd(idx)=rffd(idx)-ud(i);  % update the state
  201. end
  202. wffd=wffd(irec,:); % sort it back to the original assignment order
  203. %disp('% *******************************');
  204. %disp('First fit decreasing (FFD) method: ')
  205. disp('Best fit (BF) method: ')
  206. disp('the assignment are:')
  207. disp(wffd)
  208.  
  209. N_feature = size(wffd,2);
  210.  
  211.  input_temp = [u' u' u' u' u' u' u' u' u' u'];
  212. % Q = [input_temp(:,1:4)]
  213. % C = wff(:,1:4);
  214. % C = logical(C);
  215. % Q(C)
  216. %show_out = input_temp(C)
  217.  
  218. for k=1:5,
  219.     fprintf('Data in Bin %d', N_feature);
  220.     B = wffd(:,k);
  221.     %A = input_input';
  222.     A = input_temp(:,k);
  223.     B = logical(B);
  224.     output_ans = A(B)
  225.    
  226.    % output_ans(k) = A(B);
  227. end
  228.  
  229.  
  230. occpffd=u*wffd;
  231. nbinffd=sum([occpffd > 0]);
  232. disp(['Total # of bins used = ' int2str(nbinffd)]);
  233. disp('the occupancy of each bin after packing are:');
  234. disp(occpffd(1:nbinffd))
  235. %disp(idx)
  236. % disp('Press any key to continue to Best fit method ...'); pause
  237.    
  238. end
  239. % ******************************************************************************* %
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247. % *******************   Best fit decreasing method  ****************************** %
  248. if chosen==0 | chosen==4,  % first fit method
  249. wffd=w; rffd=r; % initialize for first fit method
  250. for i=1:n,
  251.    % disp(['ud(' int2str(i) ') = ' int2str(ud(i))]);
  252.    % disp('r = '); disp(rffd);
  253.    idx=min(find([ud(i)*ones(1,n)<=rffd]));
  254.    % disp(['u(' int2str(i) ') is assigned to b(' int2str(idx) ');']);
  255.    wffd(i,idx)=1; rffd(idx)=rffd(idx)-ud(i);  % update the state
  256. end
  257. wffd=wffd(irec,:); % sort it back to the original assignment order
  258. %disp('% *******************************');
  259. %disp('First fit decreasing (FFD) method: ')
  260. disp('Best fit (BF) method: ')
  261. disp('the assignment are:')
  262. disp(wffd)
  263.  
  264.  
  265. N_feature = size(wffd,2);
  266.  
  267.  input_temp = [u' u' u' u' u' u' u' u' u' u'];
  268. % Q = [input_temp(:,1:4)]
  269. % C = wff(:,1:4);
  270. % C = logical(C);
  271. % Q(C)
  272. %show_out = input_temp(C)
  273.  
  274. for k=1:N_feature,
  275.     fprintf('Data in Bin %d', k);
  276.     B = wffd(:,k);
  277.     %A = input_input';
  278.     A = input_temp(:,k);
  279.     B = logical(B);
  280.     output_ans = A(B)
  281.    
  282.    % output_ans(k) = A(B);
  283. end
  284.  
  285.  
  286. occpffd=u*wffd;
  287. nbinffd=sum([occpffd > 0]);
  288. disp(['Total # of bins used = ' int2str(nbinffd)]);
  289. disp('the occupancy of each bin after packing are:');
  290. disp(occpffd(1:nbinffd))
  291. %disp(idx)
  292. % disp('Press any key to continue to Best fit method ...'); pause
  293.    
  294. end
  295. % ******************************************************************************* %
Add Comment
Please, Sign In to add comment