Best-fit bin packing
ಬೆಸ್ಟ್-ಫಿಟ್ ಎಂಬುದು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗಾಗಿ ಆನ್ಲೈನ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಇದರ ಇನ್ಪುಟ್ ವಿವಿಧ ಗಾತ್ರದ ವಸ್ತುಗಳ ಪಟ್ಟಿಯಾಗಿದೆ. ಇದರ ಉತ್ಪಾದನೆಯು ಒಂದು ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ-ಪ್ರತಿ ಡಬ್ಬಿಯಲ್ಲಿನ ವಸ್ತುಗಳ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದುವಂತಹ ಸ್ಥಿರ ಸಾಮರ್ಥ್ಯದ ಡಬ್ಬಿಗಳಾಗಿ ವಸ್ತುಗಳನ್ನು ವಿಭಜಿಸುವುದು. ಆದರ್ಶಪ್ರಾಯವಾಗಿ, ನಾವು ಸಾಧ್ಯವಾದಷ್ಟು ಕಡಿಮೆ ತೊಟ್ಟಿಗಳನ್ನು ಬಳಸಲು ಬಯಸುತ್ತೇವೆ, ಆದರೆ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಎನ್ಪಿ-ಕಠಿಣ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಅತ್ಯುತ್ತಮವಾದ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅನ್ನು ಬಳಸುತ್ತದೆಃ ಇದು ತೆರೆದ ತೊಟ್ಟಿಗಳ ಪಟ್ಟಿಯನ್ನು ಇಡುತ್ತದೆ, ಅದು ಆರಂಭದಲ್ಲಿ ಖಾಲಿಯಾಗಿರುತ್ತದೆ. ಒಂದು ವಸ್ತುವು ಬಂದಾಗ, ಆ ವಸ್ತುವು ಯಾವುದಾದರೂ ಇದ್ದರೆ ಅದಕ್ಕೆ ಸರಿಹೊಂದಬಹುದಾದ ಗರಿಷ್ಠ ಹೊರೆ ಇರುವ ಡಬ್ಬಿಯನ್ನು ಅದು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಅಂತಹ ತೊಟ್ಟಿ ಕಂಡುಬಂದರೆ, ಹೊಸ ವಸ್ತುವನ್ನು ಅದರೊಳಗೆ ಇರಿಸಲಾಗುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಹೊಸ ಡಬ್ಬಿಯನ್ನು ತೆರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಬರುವ ವಸ್ತುವನ್ನು ಅದರೊಳಗೆ ಇರಿಸಲಾಗುತ್ತದೆ. ಅಂದಾಜು ಅನುಪಾತವು ಬಿಎಫ್ (ಎಲ್) ನಿಂದ ಬೆಸ್ಟ್-ಫಿಟ್ ಬಳಸುವ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ ಮತ್ತು ಒಪಿಟಿ (ಎಲ್) ನಿಂದ ಎಲ್ ಪಟ್ಟಿಗೆ ಸಾಧ್ಯವಾದಷ್ಟು ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಬಿಎಫ್ (ಎಲ್) ವಿಶ್ಲೇಷಣೆಯನ್ನು ಹಲವಾರು ಹಂತಗಳಲ್ಲಿ ಮಾಡಲಾಗಿದೆ. ಮೊದಲ ಮೇಲಿನ ಮಿತಿಯನ್ನು 1971 ರಲ್ಲಿ ಉಲ್ಮನ್ ಸಾಬೀತುಪಡಿಸಿದರು. ಗ್ಯಾರಿ, ಗ್ರಹಾಂ ಮತ್ತು ಉಲ್ಮನ್, ಜಾನ್ಸನ್ ಮತ್ತು ಡೆಮರ್ಸ್ ಅವರು ಸುಧಾರಿತ ಮೇಲ್ ಬೌಂಡ್ ಅನ್ನು ಸಾಬೀತುಪಡಿಸಿದರು. ನಂತರ, ಇದನ್ನು ಗರೆ, ಗ್ರಹಾಂ, ಜಾನ್ಸನ್, ಉಲ್ಮನ್, ಯಾವೊ ಮತ್ತು ಚಿ-ಚಿಹ್ ಅವರು ಸುಧಾರಿಸಿದರು. ಅಂತಿಮವಾಗಿ ಈ ಮಿತಿಯನ್ನು ದೋಸಾ ಮತ್ತು ಸ್ಗಾಲ್ ಅವರು ಸುಧಾರಿಸಿದರು. ಅವರು ಒಂದು ಉದಾಹರಣೆ ಇನ್ಪುಟ್ ಪಟ್ಟಿಯನ್ನು ಸಹ ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಅದು ಈ ಮಿತಿಯೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆ. ಕೆಟ್ಟ-ಹೊಂದಿಕೆಯಾಗುವ ಕೆಟ್ಟ-ಹೊಂದಿಕೆಯು ಅತ್ಯುತ್ತಮ-ಹೊಂದಿಕೆಯಾಗುವ "ಡ್ಯುಯಲ್" ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆಃ ಇದು ಮುಂದಿನ ವಸ್ತುವನ್ನು ಕನಿಷ್ಠ ಭಾರದೊಂದಿಗೆ ಡಬ್ಬಿಯಲ್ಲಿ ಇರಿಸಲು ಪ್ರಯತ್ನಿಸುತ್ತದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ನೆಕ್ಸ್ಟ್-ಫಿಟ್ನಂತೆ ಕೆಟ್ಟದಾಗಿ ವರ್ತಿಸಬಹುದು ಮತ್ತು ಅದಕ್ಕಾಗಿ ಕೆಟ್ಟ-ಕೇಸ್ ಪಟ್ಟಿಯಲ್ಲಿ ಹಾಗೆ ಮಾಡುತ್ತದೆ. ಇದಲ್ಲದೆ, ಅದು ಅದನ್ನು ಹೊಂದಿದೆ. ವರ್ಸ್ಟ್-ಫಿಟ್ ಎಂಬುದು ಎನಿಫಿಟ್-ಅಲ್ಗಾರಿದಮ್ ಆಗಿರುವುದರಿಂದ, ಅಂತಹ ಎನಿಫಿಟ್-ಅಲ್ಗಾರಿದಮ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್