First-fit bin packing
ಫಸ್ಟ್-ಫಿಟ್ (ಎಫ್ಎಫ್) ಎಂಬುದು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗಾಗಿ ಆನ್ಲೈನ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಇದರ ಇನ್ಪುಟ್ ವಿವಿಧ ಗಾತ್ರದ ವಸ್ತುಗಳ ಪಟ್ಟಿಯಾಗಿದೆ. ಇದರ ಉತ್ಪಾದನೆಯು ಒಂದು ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ-ಪ್ರತಿ ಡಬ್ಬಿಯಲ್ಲಿನ ವಸ್ತುಗಳ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದುವಂತಹ ಸ್ಥಿರ ಸಾಮರ್ಥ್ಯದ ಡಬ್ಬಿಗಳಾಗಿ ವಸ್ತುಗಳನ್ನು ವಿಭಜಿಸುವುದು. ಆದರ್ಶಪ್ರಾಯವಾಗಿ, ನಾವು ಸಾಧ್ಯವಾದಷ್ಟು ಕಡಿಮೆ ತೊಟ್ಟಿಗಳನ್ನು ಬಳಸಲು ಬಯಸುತ್ತೇವೆ, ಆದರೆ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಎನ್ಪಿ-ಕಠಿಣ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಫಸ್ಟ್-ಫಿಟ್ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅನ್ನು ಬಳಸುತ್ತದೆಃ ಇದು ತೆರೆದ ತೊಟ್ಟಿಗಳ ಪಟ್ಟಿಯನ್ನು ಇಡುತ್ತದೆ, ಅದು ಆರಂಭದಲ್ಲಿ ಖಾಲಿಯಾಗಿರುತ್ತದೆ. ಒಂದು ವಸ್ತುವು ಬಂದಾಗ, ಆ ವಸ್ತುವು ಯಾವುದಾದರೂ ಇದ್ದರೆ ಅದಕ್ಕೆ ಹೊಂದಿಕೊಳ್ಳಬಹುದಾದ ಮೊದಲ ಡಬ್ಬಿಯನ್ನು ಹುಡುಕಿ. ಅಂತಹ ತೊಟ್ಟಿ ಕಂಡುಬಂದರೆ, ಹೊಸ ವಸ್ತುವನ್ನು ಅದರೊಳಗೆ ಇರಿಸಲಾಗುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಹೊಸ ಡಬ್ಬಿಯನ್ನು ತೆರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಬರುವ ವಸ್ತುವನ್ನು ಅದರೊಳಗೆ ಇರಿಸಲಾಗುತ್ತದೆ. ಅಂದಾಜು ಅನುಪಾತವು ಎಫ್ಎಫ್ (ಎಲ್) ನಿಂದ ಫಸ್ಟ್-ಫಿಟ್ ಬಳಸುವ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ ಮತ್ತು ಒಪಿಟಿ (ಎಲ್) ನಿಂದ ಎಲ್ ಪಟ್ಟಿಗೆ ಸಾಧ್ಯವಾದಷ್ಟು ಅತ್ಯುತ್ತಮ ಸಂಖ್ಯೆಯ ತೊಟ್ಟಿಗಳನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಎಫ್ಎಫ್ (ಎಲ್) ವಿಶ್ಲೇಷಣೆಯನ್ನು ಹಲವಾರು ಹಂತಗಳಲ್ಲಿ ಮಾಡಲಾಗಿದೆ. ಎಫ್ಎಫ್ನ ಮೊದಲ ಮೇಲಿನ ಮಿತಿಯನ್ನು 1971ರಲ್ಲಿ ಉಲ್ಮನ್ ಸಾಬೀತುಪಡಿಸಿದರು. 1972ರಲ್ಲಿ, ಈ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಗ್ಯಾರಿ, ಗ್ರಹಾಂ ಮತ್ತು ಉಲ್ಮನ್, ಜಾನ್ಸನ್ ಮತ್ತು ಡೆಮರ್ಸ್ ಸುಧಾರಿಸಿದರು. 1976 ರಲ್ಲಿ, ಇದನ್ನು ಗರೆ, ಗ್ರಹಾಂ, ಜಾನ್ಸನ್, ಯಾವೊ ಮತ್ತು ಚಿ-ಚಿಹ್ ಅವರು ಸುಧಾರಿಸಿದರು, ಇದು ಮತ್ತು ನ ಅವಿಭಾಜ್ಯತೆಯ ಕಾರಣದಿಂದಾಗಿ ಸಮಾನವಾಗಿದೆ. 2010 ರಲ್ಲಿ ಕ್ಸಿಯಾ ಮತ್ತು ಟಾನ್ ಅವರ ಮುಂದಿನ ಸುಧಾರಣೆಯು ಮಿತಿಯನ್ನು ಕಡಿಮೆ ಮಾಡಿತು. ಅಂತಿಮವಾಗಿ, 2013 ರಲ್ಲಿ, ಈ ಮಿತಿಯನ್ನು ಡೋಸಾ ಮತ್ತು ಸ್ಗಾಲ್ ಸುಧಾರಿಸಿದರು. ಅವರು ಒಂದು ಉದಾಹರಣೆ ಇನ್ಪುಟ್ ಪಟ್ಟಿಯನ್ನು ಸಹ ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಇದಕ್ಕಾಗಿ ಇದು ಈ ಮಿತಿಯನ್ನು ಹೊಂದಿಸುತ್ತದೆ. ಕೆಳಗೆ ನಾವು ಪುರಾವೆಯ ಕಲ್ಪನೆಯನ್ನು ವಿವರಿಸುತ್ತೇವೆ. ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವು ಗರಿಷ್ಠ 2 ಎಂಬುದು ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವು ಗರಿಷ್ಠ 2 ಎಂಬುದಕ್ಕೆ ಪುರಾವೆಯಾಗಿದೆ. ಒಂದೂವರೆ ಭಾಗಕ್ಕಿಂತ ಕಡಿಮೆ ಮೊತ್ತದ ಎಫ್. ಎಫ್. ಬಿನ್ ಇದ್ದರೆ, ಉಳಿದ ಎಲ್ಲಾ ವಸ್ತುಗಳ ಗಾತ್ರವು ಒಂದೂವರೆ ಭಾಗಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಈ ಕೆಳಗಿನ ಎಲ್ಲಾ ಬಿನ್ಗಳ ಮೊತ್ತವು ಒಂದೂವರೆ ಭಾಗಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಗರಿಷ್ಠ ಒಂದನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಎಫ್ಎಫ್ ತೊಟ್ಟಿಗಳು ಕನಿಷ್ಠ ಅರ್ಧದಷ್ಟು ಮೊತ್ತವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಎಲ್ಲಾ ಅತ್ಯುತ್ತಮ ತೊಟ್ಟಿಗಳು ಗರಿಷ್ಠ 1 ಮೊತ್ತವನ್ನು ಹೊಂದಿರುತ್ತವೆ, ಆದ್ದರಿಂದ ಎಲ್ಲಾ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಒಪಿಟಿ ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಎಫ್ಎಫ್ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 1 + ಒಪಿಟಿ/(1/2) = 2 * ಒಪಿಟಿ + 1 ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವು ಗರಿಷ್ಠ 1.75 ಆಗಿರುತ್ತದೆ. 2/3ಕ್ಕಿಂತ ಕಡಿಮೆ ಮೊತ್ತದ ಎಫ್. ಎಫ್. ಬಿನ್ ಇದ್ದರೆ, ಉಳಿದ ಎಲ್ಲಾ ವಸ್ತುಗಳ ಗಾತ್ರವು 1/3ಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಗಾತ್ರಗಳು ಗರಿಷ್ಠ 1/2 ಆಗಿರುವುದರಿಂದ, ಕೆಳಗಿನ ಎಲ್ಲಾ ತೊಟ್ಟಿಗಳು (ಬಹುಶಃ ಕೊನೆಯದನ್ನು ಹೊರತುಪಡಿಸಿ) ಕನಿಷ್ಠ ಎರಡು ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಮೊತ್ತವು 2/3 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಗರಿಷ್ಠ ಒಂದನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಎಫ್ಎಫ್ ತೊಟ್ಟಿಗಳು ಕನಿಷ್ಠ 2/3 ಮೊತ್ತವನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಎಫ್ಎಫ್ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 2 + ಒಪಿಟಿ/(2/3) = 3/2 * ಒಪಿಟಿ + 1 ಆಗಿರುತ್ತದೆ. "ಸಮಸ್ಯಾತ್ಮಕ" ವಸ್ತುಗಳು ಎಂದರೆ ಅರ್ಧಕ್ಕಿಂತ ದೊಡ್ಡ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುವ ವಸ್ತುಗಳು. ಆದ್ದರಿಂದ, ವಿಶ್ಲೇಷಣೆಯನ್ನು ಸುಧಾರಿಸಲು, ಅರ್ಧಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ಪ್ರತಿಯೊಂದು ವಸ್ತುವಿಗೆ ಆರ್ ಬೋನಸ್ ಅನ್ನು ನೀಡೋಣ. ಒಂದು ವಸ್ತುವಿನ ತೂಕವನ್ನು ಅದರ ಗಾತ್ರ ಮತ್ತು ಅದರ ಬೋನಸ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಿ. ವಸ್ತುಗಳ ಗುಂಪಿನ ತೂಕವನ್ನು ಅದರ ವಸ್ತುಗಳ ತೂಕದ ಮೊತ್ತ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಿ. ಈಗ, ಒಂದು ವಸ್ತುವಿನೊಂದಿಗಿನ ಪ್ರತಿ ಎಫ್. ಎಫ್. ಡಬ್ಬಿಯ ತೂಕವು (ಗರಿಷ್ಠ ಒಂದನ್ನು ಹೊರತುಪಡಿಸಿ) ಕನಿಷ್ಠ 1/2 + ಆರ್ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳೊಂದಿಗಿನ ಪ್ರತಿ ಎಫ್. ಎಫ್. ಡಬ್ಬಿಯ ತೂಕವು (ಗರಿಷ್ಠ ಒಂದನ್ನು ಹೊರತುಪಡಿಸಿ) 2/3 ಆಗಿರುತ್ತದೆ. ಆರ್ = 1/6 ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದರಿಂದ ಎಲ್ಲಾ ಎಫ್ಎಫ್ ತೊಟ್ಟಿಗಳ ತೂಕವು ಕನಿಷ್ಠ 2/3 ಆಗಿರುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ಸೂಕ್ತವಾದ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿರುವ ಪ್ರತಿ ಬಿನ್ನ ತೂಕವು ಗರಿಷ್ಠ 1 + ಆರ್ = 7/6 ಆಗಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಅಂತಹ ಪ್ರತಿಯೊಂದು ಬಿನ್ ಗರಿಷ್ಠ ಒಂದು ವಸ್ತುವನ್ನು 1/2 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಎಲ್ಲಾ ವಸ್ತುಗಳ ಒಟ್ಟು ತೂಕವು ಗರಿಷ್ಠ 7/6 * ಒಪಿಟಿ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಎಫ್ಎಫ್ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 2 + (7/6 * ಒಪಿಟಿ/(2/3)) = 7/4 * ಒಪಿಟಿ + 2 ಆಗಿರುತ್ತದೆ. ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವು ಗರಿಷ್ಠ 1.7 ಈ ಕೆಳಗಿನ ಪುರಾವೆಯಿಂದ ಅಳವಡಿಸಿಕೊಳ್ಳಲಾಗಿದೆ. ಇನ್ಪುಟ್ ಐಟಂನ ತೂಕವನ್ನು ಐಟಂ ಗಾತ್ರ x ಕೆಲವು ಬೋನಸ್ ಎಂದು ಈ ಕೆಳಗಿನಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಿಃ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಅಂದಾಜು ಅನುಪಾತವು ಎರಡು ಹಕ್ಕುಗಳಿಂದ ಅನುಸರಿಸುತ್ತದೆಃ ಅತ್ಯುತ್ತಮ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿ, ಪ್ರತಿ ಬಿನ್ನ ತೂಕವು ಗರಿಷ್ಠ 17/12 ಆಗಿರುತ್ತದೆ; ಫಸ್ಟ್-ಫಿಟ್ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿ, ಪ್ರತಿ ಬಿನ್ನ ಸರಾಸರಿ ತೂಕವು ಕನಿಷ್ಠ 5/6 = 10/12 ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಲಕ್ಷಣರಹಿತವಾಗಿ, ಎಫ್ಎಫ್ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿನ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 17/10 * ಒಪಿಟಿ ಆಗಿರಬೇಕು. ಕ್ಲೈಮ್ 1 ಗೆ, ಗರಿಷ್ಠ 1 ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ಸೆಟ್ ಬಿ ಗೆ, ಬೋನಸ್ (ಬಿ) ಗರಿಷ್ಠ 5/12 ಎಂದು ಸಾಬೀತುಪಡಿಸಲು ಸಾಕು. ವಾಸ್ತವವಾಗಿಃ 'ಬಿ' ಯು 1/2ಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ಯಾವುದೇ ವಸ್ತುವನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ, ಅದು 1/6ಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ಗರಿಷ್ಠ ಐದು ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದರ ಬೋನಸ್ ಗರಿಷ್ಠ 1/12 ಆಗಿರುತ್ತದೆ; 'ಬಿ' ಯು 1/2ಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ವಸ್ತುವನ್ನು ಹೊಂದಿದ್ದರೆ ಆದರೆ [1/3,1 2] ನಲ್ಲಿ ಯಾವುದೇ ವಸ್ತುವನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ, ಅದು (1/6,1 3) ನಲ್ಲಿ ಗರಿಷ್ಠ ಎರಡು ವಸ್ತುಗಳಿಗೆ ಸ್ಥಳಾವಕಾಶವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಮತ್ತು ಅವರ ಬೋನಸ್ಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ (1/2/2-1/6) = 1/12, ಆದ್ದರಿಂದ ಒಟ್ಟು ಬೋನಸ್ 4/12 + 1/12 = 5/12 ಆಗಿರುತ್ತದೆ. ಒಂದು ವೇಳೆ 'ಬಿ' ಯು 1/2ಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ವಸ್ತುವನ್ನು ಮತ್ತು [1/3,1 2] ನಲ್ಲಿ ಒಂದು ವಸ್ತುವನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು 1/6ಕ್ಕಿಂತ ದೊಡ್ಡ ಗಾತ್ರದ ವಸ್ತುಗಳಿಗೆ ಹೆಚ್ಚು ಸ್ಥಳಾವಕಾಶವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ, ಆದ್ದರಿಂದ ಒಟ್ಟು ಬೋನಸ್ ಮತ್ತೆ 4/12+1 12 = 5/12 ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಬಿ ಯ ತೂಕವು ಗರಿಷ್ಠ 1 + 5/12 = 17/12 ಆಗಿರುತ್ತದೆ. ಕ್ಲೈಮ್ 2 ಗಾಗಿ, ಮೊದಲು ಒಂದೇ ವಸ್ತುವನ್ನು ಹೊಂದಿರುವ ಎಫ್. ಎಫ್. ಬಿನ್ ಬಿ ಅನ್ನು ಪರಿಗಣಿಸಿ. ಮೊತ್ತವು (ಬಿ) <1/2 ಆಗಿದ್ದರೆ, ಆಗ-ಎಫ್ಎಫ್ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ರೀತಿಯಲ್ಲಿ-ಬಿ ನಂತರ ಸಂಸ್ಕರಿಸಿದ ಎಲ್ಲಾ ವಸ್ತುಗಳು 1/2 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರಬೇಕು (ಇಲ್ಲದಿದ್ದರೆ ಅವುಗಳನ್ನು ಬಿ ಗೆ ಸೇರಿಸಲಾಗುತ್ತಿತ್ತು). ಆದ್ದರಿಂದ, ಮೊತ್ತ <1/2 ರಷ್ಟಿರುವ ಗರಿಷ್ಠ ಒಂದು ಎಫ್. ಎಫ್. ಬಿನ್ ಇರುತ್ತದೆ. ಈಗ ಮೊತ್ತ (ಬಿ)> 1/2 ರೊಂದಿಗೆ ಒಂದೇ ವಸ್ತುವಿನೊಂದಿಗೆ ಇತರ ಎಲ್ಲಾ ಬಿ ಡಬ್ಬಿಗಳನ್ನು ಪರಿಗಣಿಸಿ. ಈ ಎಲ್ಲಾ ತೊಟ್ಟಿಗಳಿಗೆ, ತೂಕ (ಬಿ)> 1/2+1 3 = 5/6. ಈಗ ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುವ ಎಫ್. ಎಫ್. ಡಬ್ಬಿಗಳನ್ನು ಪರಿಗಣಿಸಿ. ಮೊತ್ತವು (ಬಿ) <2/3 ಆಗಿದ್ದರೆ, ನಂತರ-ಎಫ್ಎಫ್ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ರೀತಿಯಲ್ಲಿ-ಬಿ ನಂತರ ಸಂಸ್ಕರಿಸಿದ ಎಲ್ಲಾ ವಸ್ತುಗಳು 1/3 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರಬೇಕು (ಇಲ್ಲದಿದ್ದರೆ ಅವುಗಳನ್ನು ಬಿ ಗೆ ಸೇರಿಸಲಾಗುತ್ತಿತ್ತು). ಆದ್ದರಿಂದ, ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಕೆಳಗಿನ ತೊಟ್ಟಿಗಳು 2/3 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತವೆ. ಆದ್ದರಿಂದ ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುವ ಗರಿಷ್ಠ ಒಂದು ಎಫ್ಎಫ್ ಬಿನ್ ಇರುತ್ತದೆ ಮತ್ತು ಮೊತ್ತವು <2/3 ಆಗಿರುತ್ತದೆ. ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಇತರ ತೊಟ್ಟಿಗಳನ್ನು ಈಗ ಪರಿಗಣಿಸಿ ಮತ್ತು ಮೊತ್ತ> 2/3. ಅವುಗಳನ್ನು ಬಿ [1], ಬಿ [2], ಬಿ [ಕೆ] ಎಂದು ಸೂಚಿಸಿ, ಅವುಗಳನ್ನು ತೆರೆಯುವ ಕ್ರಮದಿಂದ ಸೂಚಿಸಿ. 1,., k ನಲ್ಲಿನ ಪ್ರತಿ i ಗೆ, B [i] ಮತ್ತು B [i + 1] ನ ಬೋನಸ್ ಮೊತ್ತವು ಕನಿಷ್ಠ 5/6 ಎಂದು ನಾವು ಸಾಬೀತುಪಡಿಸುತ್ತೇವೆಃ ಮೊತ್ತ (B [i]) + ಬೋನಸ್ (B [i + 1])> = 5/6. ವಾಸ್ತವವಾಗಿ, ಮೊತ್ತವು (ಬಿ [ಐ])> = 5/6 ಆಗಿದ್ದರೆ, ಅಸಮಾನತೆಯು ಕ್ಷುಲ್ಲಕವಾಗಿರುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಮೊತ್ತವು (ಬಿ [ಐ]): = 1-x ಆಗಿರಲಿ. x ಎಂಬುದು 1/6 ಮತ್ತು 2/6ರ ನಡುವೆ ಇದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಏಕೆಂದರೆ ಮೊತ್ತವು (B [i]) 2/3 ಮತ್ತು 5/6ರ ನಡುವೆ ಇರುತ್ತದೆ. ಬಿ [ಐ + 1] ಅನ್ನು ಬಿ [ಐ] ನಂತರ ತೆರೆಯುವುದರಿಂದ, ಬಿ [ಐ + 1] ಕನಿಷ್ಠ ಎರಡು ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಉದಾಹರಣೆಗೆ ಸಿ1 ಮತ್ತು ಸಿ2, ಅವು ಬಿ [ಐ] ಗೆ ಹೊಂದಿಕೆಯಾಗುವುದಿಲ್ಲ, ಅಂದರೆಃ ಸಿ1, ಸಿ2> 1-ಮೊತ್ತ (ಬಿ [ಐ]) = x> 1/6. ನಂತರ ಸಿ1 ಮತ್ತು ಸಿ2 ಎರಡರ ಬೋನಸ್ ಕನಿಷ್ಠ x/2-1/12 ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, B [i + 1] ನ ಬೋನಸ್ ಕನಿಷ್ಠ x-1/6 ಆಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಮೊತ್ತ (B [i]) + ಬೋನಸ್ (B [i + 1])> = (1-x) + (x-1/6) = 5/6 ಆಗಿರುತ್ತದೆ. ಮೇಲಿನ ಅಸಮಾನತೆಯನ್ನು ನಾವು ಅನುಕ್ರಮ ಜೋಡಿಗಳಿಗೆ ಅನ್ವಯಿಸಬಹುದು ಮತ್ತು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಪಡೆಯಬಹುದುಃ ಮೊತ್ತ (ಬಿ [1]) + ಬೋನಸ್ (ಬಿ [2]) + ಮೊತ್ತ (ಬಿ [2]) + ಬೋನಸ್ (ಬಿ [3]) + + ಮೊತ್ತ (ಬಿ [ಕೆ-1]) + ಬೋನಸ್ (ಬಿ [ಕೆ])> = 5/6 * (ಕೆ-1). ಆದ್ದರಿಂದ, ಎಲ್ಲಾ ಎಫ್. ಎಫ್. ಡಬ್ಬಿಗಳ ಒಟ್ಟು ತೂಕವು ಕನಿಷ್ಠ 5/6 * (ಎಫ್. ಎಫ್.-3) ಆಗಿರುತ್ತದೆ (ಇಲ್ಲಿ ನಾವು ಒಂದೇ ಒಂದು-ಐಟಂ ಬಿನ್ಗೆ 3 ಅನ್ನು ಮೊತ್ತ <1/2, ಏಕ ಎರಡು-ಐಟಂ ಬಿನ್ ಅನ್ನು ಮೊತ್ತ <2/3, ಮತ್ತು ಎರಡು-ಐಟಂ ಬಿನ್ಗಳಿಂದ ಕೆ-1 ಅನ್ನು ಮೊತ್ತ> = 2/3). ಒಟ್ಟಾರೆಯಾಗಿ, ನಾವು 17/12 * OPT> = 5/6 * (FF-3) ಅನ್ನು ಪಡೆಯುತ್ತೇವೆ, ಆದ್ದರಿಂದ FF <= 17/10 * OPT + 3. ಡೋಸಾ ಮತ್ತು ಸ್ಗಾಲ್ ಕಠಿಣವಾದ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಅದು 3 ಅನ್ನು ತೊಡೆದುಹಾಕುತ್ತದೆ ಮತ್ತು ಆ ಎಫ್ಎಫ್ <= 17/10 * ಒಪಿಟಿ ಅನ್ನು ಪಡೆಯುತ್ತದೆ. 1.7OPT ನ ಕಾರ್ಯಕ್ಷಮತೆಯ ಬಂಧವು ಬಿಗಿಯಾಗಿರುವ ನಿದರ್ಶನಗಳಿವೆ. ಈ ಕೆಳಗಿನ ಉದಾಹರಣೆಯು ಇದನ್ನು ಆಧರಿಸಿದೆ. ಬಿನ್ ಸಾಮರ್ಥ್ಯವು 101, ಮತ್ತುಃ ಅನುಕ್ರಮವುಃ 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10). ಅತ್ಯುತ್ತಮ ಪ್ಯಾಕಿಂಗ್ 10 ತೊಟ್ಟಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆಃ [51+34 + 16] (x3), [51+34 + 10+6] (x7). ಎಲ್ಲಾ ಬಿನ್ ಮೊತ್ತಗಳು 101 ಆಗಿವೆ. ಫಸ್ಟ್ ಫಿಟ್ ಪ್ಯಾಕಿಂಗ್ 17 ತೊಟ್ಟಿಗಳನ್ನು ಹೊಂದಿದೆಃ [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10). ಬಿನ್ ಮೊತ್ತಗಳುಃ 92,68,68 (x5), 51 (x10). ಬಹುಮಾನಗಳು (101ಕ್ಕೆ ಸಾಮಾನ್ಯ) 0,0,16.8 (x5), 33.7 (x10) ಆಗಿವೆ. ಒಟ್ಟು ತೂಕಗಳು (101ಕ್ಕೆ ಸಾಮಾನ್ಯ) 92,68,84.8 (x5), 84.7 (x10) ಆಗಿವೆ. ಬಹುತೇಕ ಎಲ್ಲಾ ತೂಕಗಳು 101 * 5/6 = 84.1 ಕ್ಕೆ ಹತ್ತಿರದಲ್ಲಿರುವುದನ್ನು ಕಾಣಬಹುದು. ರಿಫೈನ್ಡ್ ಫಸ್ಟ್-ಫಿಟ್ ರಿಫೈನ್ಡ್-ಫಸ್ಟ್-ಫಿಟ್ (ಆರ್ಎಫ್ಎಫ್) ಎಂಬುದು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗಾಗಿ ಮತ್ತೊಂದು ಆನ್ಲೈನ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು, ಇದು ಹಿಂದೆ ಅಭಿವೃದ್ಧಿಪಡಿಸಿದ ಎಫ್ಎಫ್ ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿ ಸುಧಾರಿಸುತ್ತದೆ. ಇದನ್ನು ಆಂಡ್ರ್ಯೂ ಚಿ-ಚಿ ಯಾವೊ ಪ್ರಸ್ತುತಪಡಿಸಿದರು. ಅಲ್ಗಾರಿದಮ್ ವಸ್ತುಗಳನ್ನು ಅವುಗಳ ಗಾತ್ರಕ್ಕೆ ಅನುಗುಣವಾಗಿ ನಾಲ್ಕು ವರ್ಗಗಳಲ್ಲಿ ವರ್ಗೀಕರಿಸಲಾಗಿದೆ (ಅಲ್ಲಿ ಬಿನ್ ಸಾಮರ್ಥ್ಯವು 1 ಆಗಿದೆ):-ತುಂಡು-ಗಾತ್ರ. - ತುಂಡು-ಗಾತ್ರ. - ತುಂಡು-ಗಾತ್ರ. - ತುಂಡು-ಗಾತ್ರ. ಅಂತೆಯೇ, ತೊಟ್ಟಿಗಳನ್ನು ನಾಲ್ಕು ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆಃ 1,2,3 ಮತ್ತು 4. ಒಂದು ಸ್ಥಿರ ಪೂರ್ಣಾಂಕವಾಗಿರಲಿ. ಮುಂದಿನ ವಸ್ತುವನ್ನು-1ನೇ ತರಗತಿಯಲ್ಲಿ, ಒಂದು-ತುಣುಕು ಆಗಿದ್ದರೆ, 2ನೇ ತರಗತಿಯಲ್ಲಿ, ಒಂದು-ತುಣುಕು ಆಗಿದ್ದರೆ, 3ನೇ ತರಗತಿಯಲ್ಲಿ, ಒಂದು-ತುಣುಕು ಆಗಿದ್ದರೆ, ಆದರೆ ಇಲ್ಲಿಯವರೆಗೆ ನೋಡಿದ ಯಾವುದೇ ಪೂರ್ಣಾಂಕಕ್ಕೆ, ಬಿನ್ನಲ್ಲಿ ನಿಗದಿಪಡಿಸಲಾಗಿದೆ. 1ನೇ ತರಗತಿಯು, ಇಲ್ಲಿಯವರೆಗೆ ಕಂಡುಬಂದಿದ್ದರೆ, 4ನೇ ತರಗತಿಯು, ಒಂದು-ಕೃತಿಯಾಗಿದ್ದರೆ. ಒಮ್ಮೆ ವಸ್ತುವಿನ ವರ್ಗವನ್ನು ಆಯ್ಕೆ ಮಾಡಿದ ನಂತರ, ಅದನ್ನು ಆ ವರ್ಗದ ತೊಟ್ಟಿಗಳ ಒಳಗೆ ಮೊದಲ-ಹೊಂದಿಕೊಳ್ಳುವ ತೊಟ್ಟಿ ಪ್ಯಾಕಿಂಗ್ ಬಳಸಿ ಇರಿಸಲಾಗುತ್ತದೆ. ಪ್ರಸ್ತುತ ವಸ್ತುವು ತೆರೆದ ತೊಟ್ಟಿಯೊಳಗೆ (ಇನ್ನೊಂದು ವರ್ಗದಿಂದ) ಹೊಂದಿಕೊಳ್ಳುತ್ತದೆಯಾದರೂ ಅದು ಹೊಸ ತೊಟ್ಟಿಯೊಂದನ್ನು ತೆರೆಯಬಹುದಾದ್ದರಿಂದ ಆರ್. ಎಫ್. ಎಫ್. ಯಾವುದೇ-ಸೂಕ್ತವಾದ ಕ್ರಮಾವಳಿ ಅಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಅಂದಾಜು ಅನುಪಾತ ಆರ್. ಎಫ್. ಎಫ್. ಅಂದಾಜು ಖಾತರಿಯನ್ನು ಹೊಂದಿದೆ. ಫಾರ್ ನೊಂದಿಗೆ ಪಟ್ಟಿಗಳ ಒಂದು ಕುಟುಂಬವಿದೆ. ಫಸ್ಟ್-ಫಿಟ್-ಡಿಕ್ರೀಸಿಂಗ್ (ಎಫ್ಎಫ್ಡಿ) ಎಂಬುದು ಫಸ್ಟ್-ಫಿಟ್ನ ಆಫ್ಲೈನ್ ರೂಪಾಂತರವಾಗಿದೆಃ ಇದು ಎಲ್ಲಾ ಇನ್ಪುಟ್ ವಸ್ತುಗಳನ್ನು ಸ್ವೀಕರಿಸುತ್ತದೆ, ಅವರೋಹಣ ಗಾತ್ರದ ಮೂಲಕ ಆದೇಶಿಸುತ್ತದೆ ಮತ್ತು ಫಸ್ಟ್-ಫಿಟ್ಗೆ ಕರೆ ಮಾಡುತ್ತದೆ. ಇದರ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಅಂದಾಜು ಅನುಪಾತವು ತುಂಬಾ ಉತ್ತಮವಾಗಿದೆಃ 1.7ರ ಬದಲಿಗೆ ಸುಮಾರು 1.222. ಅನುಷ್ಠಾನಗಳು ಪೈಥಾನ್ಃ ಪ್ರಾಟಿಪಿ ಪ್ಯಾಕೇಜ್ ಮೊದಲ-ಫಿಟ್ನ ಅನುಷ್ಠಾನವನ್ನು ಒಳಗೊಂಡಿದೆ. ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್