Karmarkar–Karp bin packing algorithms
ಕರ್ಮಾರ್ಕರ್-ಕಾರ್ಪ್ (ಕೆಕೆ) ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಕ್ರಮಾವಳಿಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಸಂಬಂಧಿಸಿದ ಹಲವಾರು ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಾಗಿವೆ. ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆಯು ವಿವಿಧ ಗಾತ್ರದ ವಸ್ತುಗಳನ್ನು ಒಂದೇ ಸಾಮರ್ಥ್ಯದ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಪ್ಯಾಕ್ ಮಾಡುವ ಸಮಸ್ಯೆಯಾಗಿದ್ದು, ಒಟ್ಟು ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದಾಗಿದೆ. ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಗಣನೆಗೆ ಕಷ್ಟಕರವಾಗಿದೆ. ಕರ್ಮಾರ್ಕರ್ ಮತ್ತು ಕಾರ್ಪ್ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ಮತ್ತು ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುವ ಕ್ರಮಾವಳಿಯನ್ನು ರೂಪಿಸಿದರು, ಅಲ್ಲಿ ಒಪಿಟಿ ಎಂದರೆ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರದಲ್ಲಿರುವ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ. ಅವರು ಸ್ವಲ್ಪ ವಿಭಿನ್ನ ಅಂದಾಜು ಖಾತರಿಗಳು ಮತ್ತು ರನ್-ಟೈಮ್ ಬೌಂಡರಿಗಳೊಂದಿಗೆ ಹಲವಾರು ಇತರ ಕ್ರಮಾವಳಿಗಳನ್ನು ಸಹ ರೂಪಿಸಿದರು. ಕೆಕೆ ಕ್ರಮಾವಳಿಗಳನ್ನು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ನ ಅಧ್ಯಯನದಲ್ಲಿ ಒಂದು ಪ್ರಗತಿ ಎಂದು ಪರಿಗಣಿಸಲಾಗಿದೆಃ ಹಿಂದೆ ತಿಳಿದಿರುವ ಕ್ರಮಾವಳಿಗಳು ಮಲ್ಟಿಪ್ಲಿಕೇಟಿವ್ ಅಂದಾಜುಗಳನ್ನು ಕಂಡುಕೊಂಡಿವೆ, ಅಲ್ಲಿ ಕೆಲವು ಸ್ಥಿರಾಂಕಗಳಿಗೆ ಅಥವಾ ಗರಿಷ್ಠವಾಗಿ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಹೆಚ್ಚಾಗಿತ್ತು. ಕೆ. ಕೆ. ಕ್ರಮಾವಳಿಗಳು ಸಂಯೋಜನೀಯ ಅಂದಾಜನ್ನು ಸಾಧಿಸಿದ ಮೊದಲ ಕ್ರಮಗಳಾಗಿವೆ. ಇನ್ಪುಟ್ ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆಯ ಇನ್ಪುಟ್ ವಿವಿಧ ಗಾತ್ರದ ವಸ್ತುಗಳ ಗುಂಪಾಗಿದೆ, a1,. an. ಈ ಕೆಳಗಿನ ಸಂಕೇತವನ್ನು ಬಳಸಲಾಗುತ್ತದೆಃ n-ವಸ್ತುಗಳ ಸಂಖ್ಯೆ. m-ವಿವಿಧ ಐಟಂ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆ. 1 ರಲ್ಲಿ ಪ್ರತಿ i ಗೆ, m: si ಎಂಬುದು i-th ಗಾತ್ರವಾಗಿದೆ; ni ಎಂಬುದು ಗಾತ್ರದ ವಸ್ತುಗಳ ಸಂಖ್ಯೆ. ಬಿ-ಬಿನ್ ಗಾತ್ರ. ಒಂದು ಉದಾಹರಣೆ I ಅನ್ನು ನೀಡಿದರೆ, ನಾವು ಸೂಚಿಸುವುದೇನೆಂದರೆಃ ಒಪಿಟಿ (ಐ) = ಉದಾಹರಣೆ I ಯ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರ. ಎಫ್ಒಪಿಟಿ (ಐ) = (ಎ1 +. + ಎ)/ಬಿ = ಸೈದ್ಧಾಂತಿಕವಾಗಿ-ಅತ್ಯುತ್ತಮ ಸಂಖ್ಯೆಯ ತೊಟ್ಟಿಗಳು, ಎಲ್ಲಾ ತೊಟ್ಟಿಗಳು ಸಂಪೂರ್ಣವಾಗಿ ವಸ್ತುಗಳು ಅಥವಾ ಐಟಂ ಭಿನ್ನರಾಶಿಗಳಿಂದ ತುಂಬಿರುವಾಗ. ನಿಸ್ಸಂಶಯವಾಗಿ, ಎಫ್ಓಪಿಟಿ (ಐ) ≤ ಒಪಿಟಿ (ಐ). ಉನ್ನತ ಮಟ್ಟದ ಯೋಜನೆಯು ಕೆ. ಕೆ. ಕ್ರಮಾವಳಿಗಳು ಮೂಲಭೂತವಾಗಿ ಸಂರಚನೆಯ ರೇಖೀಯ ಕ್ರಮಾವಳಿಯನ್ನು ಪರಿಹರಿಸುತ್ತವೆಃ ಇಲ್ಲಿ, ಎ ಎಂಬುದು m ಸಾಲುಗಳನ್ನು ಹೊಂದಿರುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ. ಎ ಯ ಪ್ರತಿಯೊಂದು ಅಂಕಣವು ಕಾರ್ಯಸಾಧ್ಯವಾದ ಸಂರಚನೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ-ಐಟಂ-ಗಾತ್ರಗಳ ಬಹು-ಸೆಟ್, ಅಂದರೆ ಈ ಎಲ್ಲಾ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಬಿ ಆಗಿರುತ್ತದೆ. ಸಂರಚನೆಗಳ ಸಮೂಹವು ಸಿ. x ಎಂಬುದು ಸಿ ಗಾತ್ರದ ವಾಹಕವಾಗಿದೆ. x ನ ಪ್ರತಿಯೊಂದು ಅಂಶ xc ಯು ಸಂರಚನೆ c ಅನ್ನು ಬಳಸಿದ ಸಂಖ್ಯೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಉದಾಹರಣೆಃ ವಸ್ತುವಿನ ಗಾತ್ರಗಳು 3,3,3,3,3,4,4,4,4,4, ಮತ್ತು B = 12 ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ ಸಿ = 10 ಸಂಭವನೀಯ ಸಂರಚನೆಗಳಿವೆಃ 3333; 333; 33,334,344; 4,44,444. ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎ ಎರಡು ಸಾಲುಗಳನ್ನು ಹೊಂದಿದೆಃ s = 3ಕ್ಕೆ [4,3,2,2,1,1,1,0,0,0] ಮತ್ತು s = 4ಕ್ಕೆ [0,0,0,1,0,1,2,1,2,3]. ಪ್ರತಿ ಗಾತ್ರದ 5 ವಸ್ತುಗಳು ಇರುವುದರಿಂದ ವಾಹಕ n [5,5] ಆಗಿದೆ. 3333, 344, 444 ಸಂರಚನೆಗಳೊಂದಿಗೆ ಮೂರು ತೊಟ್ಟಿಗಳನ್ನು ಬಳಸುವುದಕ್ಕೆ ಅನುಗುಣವಾದ ಸಂಭಾವ್ಯ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವೆಂದರೆ x = [1,0,0,0,0,0,1,0,0,1]. ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವಲ್ಲಿ ಎರಡು ಪ್ರಮುಖ ಸಮಸ್ಯೆಗಳಿವೆ. ಮೊದಲನೆಯದಾಗಿ, ಇದು ಒಂದು ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಆಗಿದ್ದು, ಇದನ್ನು ಪರಿಹರಿಸಲು ಗಣನೆಗೆ ಕಷ್ಟವಾಗುತ್ತದೆ. ಎರಡನೆಯದಾಗಿ, ಅಸ್ಥಿರಗಳ ಸಂಖ್ಯೆ ಸಿ-ಸಂರಚನೆಗಳ ಸಂಖ್ಯೆ, ಇದು ಅಗಾಧವಾಗಿರಬಹುದು. ಕೆಕೆ ಕ್ರಮಾವಳಿಗಳು ಹಲವಾರು ತಂತ್ರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಈ ತೊಂದರೆಗಳನ್ನು ನಿಭಾಯಿಸುತ್ತವೆ, ಅವುಗಳಲ್ಲಿ ಕೆಲವನ್ನು ಈಗಾಗಲೇ ಡಿ-ಲಾ-ವೇಗಾ ಮತ್ತು ಲ್ಯೂಕರ್ ಪರಿಚಯಿಸಿದ್ದಾರೆ. ಅಲ್ಗಾರಿದಮ್ನ ಉನ್ನತ ಮಟ್ಟದ ವಿವರಣೆ ಇಲ್ಲಿದೆ (ಮೂಲ ಉದಾಹರಣೆ ಎಲ್ಲಿದೆ): 1-ಎ. ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ನಿರ್ಮಿಸಲಾದ ಒಂದು ಉದಾಹರಣೆಯಾಗಿರಲಿ. 2-ಎ. ವಸ್ತುಗಳನ್ನು ವರ್ಗೀಕರಿಸುವ ಮೂಲಕ ಮತ್ತು ಪ್ರತಿ ಗುಂಪಿನಲ್ಲಿನ ವಸ್ತುಗಳ ಗಾತ್ರವನ್ನು ಗುಂಪಿನಲ್ಲಿನ ಅತ್ಯುನ್ನತ ವಸ್ತುವಿಗೆ ಪೂರ್ಣಾಂಕಿಸುವ ಮೂಲಕ ನಿರ್ಮಿಸಲಾದ ಒಂದು ಉದಾಹರಣೆಯಾಗಿರಲಿ. 3-ಎ. ಸಮಗ್ರತೆಯ ನಿರ್ಬಂಧಗಳಿಲ್ಲದೆ ಸಂರಚನೆಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ರಚಿಸಿ. 4. ಸಡಿಲವಾದ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂಗಾಗಿ a (ಭಾಗಶಃ) ಪರಿಹಾರ x ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. 3-ಬಿ. ಒಂದು ಅವಿಭಾಜ್ಯ ಪರಿಹಾರಕ್ಕೆ x ಅನ್ನು ಸುತ್ತಿಕೊಳ್ಳಿ. 2-ಬಿ. ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು ವಸ್ತುಗಳನ್ನು "ಅನ್-ಗ್ರೂಪ್" ಮಾಡಿ. 1-ಬಿ. ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಸೇರಿಸಿ. ಕೆಳಗೆ, ನಾವು ಈ ಪ್ರತಿಯೊಂದು ಹಂತಗಳನ್ನು ಅನುಕ್ರಮವಾಗಿ ವಿವರಿಸುತ್ತೇವೆ. ಹಂತ 1. ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದು ಮತ್ತು ಸೇರಿಸುವುದು ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಪ್ರೇರಣೆಯೆಂದರೆ, ಎಲ್ಲಾ ವಸ್ತುಗಳು ದೊಡ್ಡದಾಗಿದ್ದಾಗ, ಪ್ರತಿ ಡಬ್ಬಿಯಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಚಿಕ್ಕದಾಗಿರಬೇಕು, ಆದ್ದರಿಂದ ಸಂಭವನೀಯ ಸಂರಚನೆಗಳ ಸಂಖ್ಯೆಯು (ತುಲನಾತ್ಮಕವಾಗಿ) ಚಿಕ್ಕದಾಗಿದೆ. ನಾವು ಕೆಲವು ಸ್ಥಿರಾಂಕಗಳನ್ನು ಆರಿಸಿಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಅದಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಎಲ್ಲಾ ವಸ್ತುಗಳನ್ನು ಮೂಲ ನಿದರ್ಶನದಿಂದ ತೆಗೆದುಹಾಕುತ್ತೇವೆ. ಇದು ಫಲಿತಾಂಶದ ಉದಾಹರಣೆಯಾಗಿರಲಿ. ಪ್ರತಿ ಬಿನ್ನಲ್ಲಿ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳು ಇರಬಹುದೆಂಬುದನ್ನು ಗಮನಿಸಿ. ನಾವು ಪ್ಯಾಕಿಂಗ್ ಮಾಡಿ ಕೆಲವು ಡಬ್ಬಿಗಳೊಂದಿಗೆ ಪ್ಯಾಕಿಂಗ್ ಅನ್ನು ಪಡೆಯುತ್ತೇವೆ. ಈಗ, ಸ್ಥಳಾವಕಾಶವಿರುವವರೆಗೆ, ಅಸ್ತಿತ್ವದಲ್ಲಿರುವ ತೊಟ್ಟಿಗಳಲ್ಲಿ ನಾವು ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಅನಿಯಂತ್ರಿತ ಕ್ರಮದಲ್ಲಿ ಸೇರಿಸುತ್ತೇವೆ. ಅಸ್ತಿತ್ವದಲ್ಲಿರುವ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಹೆಚ್ಚು ಸ್ಥಳಾವಕಾಶವಿಲ್ಲದಿದ್ದಾಗ, ನಾವು ಹೊಸ ತೊಟ್ಟಿ ತೆರೆಯುತ್ತೇವೆ (ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿರುವಂತೆ). ಅಂತಿಮ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ. ನಂತರಃ. ಪ್ರೂಫ್. ಯಾವುದೇ ಹೊಸ ತೊಟ್ಟಿಗಳನ್ನು ತೆರೆಯದಿದ್ದರೆ, ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ ಉಳಿಯುತ್ತದೆ. ಹೊಸ ಬಿನ್ ಅನ್ನು ತೆರೆದರೆ, ಬಹುಶಃ ಕೊನೆಯದನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಬಿನ್ಗಳು ಕನಿಷ್ಠ ಒಟ್ಟು ಗಾತ್ರವನ್ನು ಹೊಂದಿರುತ್ತವೆ, ಆದ್ದರಿಂದ ಒಟ್ಟು ಉದಾಹರಣೆಯ ಗಾತ್ರವು ಕನಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಅತ್ಯುತ್ತಮ ಪರಿಹಾರಕ್ಕೆ ಕನಿಷ್ಠ ತೊಟ್ಟಿಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. ಆದ್ದರಿಂದ. ನಿರ್ದಿಷ್ಟವಾಗಿ, g = 1/n ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ, ನಾವು ಪಡೆಯುತ್ತೇವೆಃ, ಏಕೆಂದರೆ. ಆದ್ದರಿಂದ, ಎಲ್ಲಾ ವಸ್ತುಗಳು 1/n ಗಿಂತ ದೊಡ್ಡದಾಗಿವೆ ಎಂದು ಭಾವಿಸುವುದು ಸಾಮಾನ್ಯವಾಗಿದೆ. ಹಂತ 2. ಐಟಂಗಳನ್ನು ಗುಂಪುಗೂಡಿಸುವುದು ಮತ್ತು ಗುಂಪುಗೂಡಿಸದಿರುವುದು ವಿವಿಧ ಐಟಂ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು, ಸಂರಚನೆ ಎಲ್ಪಿಯಲ್ಲಿನ ನಿರ್ಬಂಧಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಐಟಂಗಳನ್ನು ಗುಂಪುಗೂಡಿಸುವ ಪ್ರೇರಣೆಯಾಗಿದೆ. ಸಾಮಾನ್ಯ ಗುಂಪು ಮಾಡುವ ಪ್ರಕ್ರಿಯೆಯೆಂದರೆಃ ಇಳಿಯುವ ಗಾತ್ರದ ಮೂಲಕ ವಸ್ತುಗಳನ್ನು ಆದೇಶಿಸಿ. ವಸ್ತುಗಳನ್ನು ಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸಿ. ಪ್ರತಿ ಗುಂಪಿಗೆ, ಗುಂಪಿನಲ್ಲಿರುವ ಎಲ್ಲಾ ವಸ್ತುಗಳ ಗಾತ್ರವನ್ನು ಗುಂಪಿನಲ್ಲಿರುವ ಅತಿದೊಡ್ಡ ಗಾತ್ರಕ್ಕೆ ಮಾರ್ಪಡಿಸಿ. ಹಲವಾರು ವಿಭಿನ್ನ ಗುಂಪು ವಿಧಾನಗಳಿವೆ. ಲೀನಿಯರ್ ಗ್ರೂಪಿಂಗ್ ಒಂದು ಪೂರ್ಣಾಂಕದ ನಿಯತಾಂಕವಾಗಿರಲಿ. ಗುಂಪು 1ರಲ್ಲಿ ಅತಿದೊಡ್ಡ ವಸ್ತುಗಳನ್ನು ಇರಿಸಿ; ಗುಂಪು 2ರಲ್ಲಿ ಮುಂದಿನ ಅತಿದೊಡ್ಡ ವಸ್ತುಗಳನ್ನು ಇರಿಸಿ; ಮತ್ತು ಹೀಗೆ (ಕೊನೆಯ ಗುಂಪಿನಲ್ಲಿ ವಸ್ತುಗಳಿಗಿಂತ ಕಡಿಮೆ ಇರಬಹುದು). ಇದು ಮೂಲ ನಿದರ್ಶನವಾಗಿರಲಿ. ಮೊದಲ ಗುಂಪು (ದೊಡ್ಡ ವಸ್ತುಗಳ ಗುಂಪು) ಮತ್ತು ಮೊದಲ ಗುಂಪು ಇಲ್ಲದ ಗುಂಪು ಉದಾಹರಣೆಯಾಗಿರಲಿ. ನಂತರಃ ಎಲ್ಲಾ ವಸ್ತುಗಳು ಒಂದೇ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ವಿವಿಧ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ. - ಗುಂಪು 1 ರಲ್ಲಿ ಗುಂಪು 2 ರಲ್ಲಿ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿರುವುದರಿಂದ (ಗುಂಪು 1 ರಲ್ಲಿನ ಎಲ್ಲಾ ಕೆ ವಸ್ತುಗಳು ಗುಂಪು 2 ರಲ್ಲಿನ ಕೆ ವಸ್ತುಗಳಿಗಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತವೆ); ಅಂತೆಯೇ, ಗುಂಪು 2 ರಲ್ಲಿ ಗುಂಪು 3 ರಲ್ಲಿ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿದೆ, ಇತ್ಯಾದಿ. - ಏಕೆಂದರೆ ಪ್ರತಿಯೊಂದು ವಸ್ತುವನ್ನು ಒಂದೇ ಡಬ್ಬಿಯಲ್ಲಿ ಕಟ್ಟಲು ಸಾಧ್ಯವಿದೆ. ಆದ್ದರಿಂದ,. ವಾಸ್ತವವಾಗಿ, ತೊಟ್ಟಿಗಳೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ನೀಡಿದರೆ, ನಾವು ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಪಡೆಯಬಹುದು. ಜ್ಯಾಮಿತೀಯ ಗುಂಪುಗಾರಿಕೆ ಒಂದು ಪೂರ್ಣಾಂಕದ ನಿಯತಾಂಕವಾಗಿರಲಿ. ಜ್ಯಾಮಿತೀಯ ಗುಂಪುಗಾರಿಕೆಯು ಎರಡು ಹಂತಗಳಲ್ಲಿ ಮುಂದುವರಿಯುತ್ತದೆಃ ನಿದರ್ಶನವನ್ನು ಹಲವಾರು ನಿದರ್ಶನಗಳಾಗಿ ವಿಭಜಿಸಿ, ಪ್ರತಿ ನಿದರ್ಶನದಲ್ಲೂ, ಎಲ್ಲಾ ಗಾತ್ರಗಳು ಮಧ್ಯಂತರದಲ್ಲಿರುತ್ತವೆ. ಎಲ್ಲಾ ವಸ್ತುಗಳು ಕನಿಷ್ಠ ಗಾತ್ರವನ್ನು ಹೊಂದಿದ್ದರೆ, ನಿದರ್ಶನಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಪ್ರತಿ ನಿದರ್ಶನದಲ್ಲೂ, ನಿಯತಾಂಕದೊಂದಿಗೆ ರೇಖೀಯ ಪೂರ್ಣಾಂಕವನ್ನು ನಿರ್ವಹಿಸಿ. ಫಲಿತಾಂಶದ ನಿದರ್ಶನಗಳಾಗಿರಲಿ. ಮತ್ತು ಆಗಲಿ. ನಂತರ, ವಿವಿಧ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಸೀಮಿತಗೊಳಿಸಲಾಗಿದೆಃ ಎಲ್ಲಾ r, ಮತ್ತು. ಎಲ್ಲಾ ವಸ್ತುಗಳು ಅದಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರುವುದರಿಂದ, ನಾವು ಅದನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಎಲ್ಲಾ r ಅನ್ನು ಒಟ್ಟುಗೂಡಿಸುವುದು ನೀಡುತ್ತದೆ. ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಸೀಮಿತಗೊಳಿಸಲಾಗಿದೆಃ ಎಲ್ಲಾ r ಗೆ,-ಏಕೆಂದರೆ ವಸ್ತುಗಳು ಇವೆ, ಮತ್ತು ಅವೆಲ್ಲವೂ ಚಿಕ್ಕದಾಗಿರುತ್ತವೆ, ಆದ್ದರಿಂದ ಅವುಗಳನ್ನು ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಪ್ಯಾಕ್ ಮಾಡಬಹುದು. ಆದ್ದರಿಂದ,. ಆದ್ದರಿಂದ,. ಪರ್ಯಾಯ ಜ್ಯಾಮಿತೀಯ ಗುಂಪುಗಾರಿಕೆ ಒಂದು ಪೂರ್ಣಾಂಕದ ನಿಯತಾಂಕವಾಗಿರಲಿ. ಗಾತ್ರವನ್ನು ಇಳಿಸುವ ಮೂಲಕ ವಸ್ತುಗಳನ್ನು ಆರ್ಡರ್ ಮಾಡಿ. ಪ್ರತಿ ಗುಂಪಿನಲ್ಲಿನ ಒಟ್ಟು ಗಾತ್ರವು ಕನಿಷ್ಠ ಇರುವಂತೆ ಅವುಗಳನ್ನು ಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸಿ. ಪ್ರತಿ ವಸ್ತುವಿನ ಗಾತ್ರವು ಬಿ ಗಿಂತ ಕಡಿಮೆಯಾಗಿರುವುದರಿಂದ, ಪ್ರತಿ ಗುಂಪಿನಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಕನಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಪ್ರತಿ ಗುಂಪಿನಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ದುರ್ಬಲವಾಗಿ ಹೆಚ್ಚುತ್ತಿದೆ. ಎಲ್ಲಾ ವಸ್ತುಗಳು ಅದಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ, ಪ್ರತಿ ಗುಂಪಿನಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಪ್ರತಿ ಗುಂಪಿನಲ್ಲಿ, ದೊಡ್ಡ ವಸ್ತುಗಳನ್ನು ಮಾತ್ರ ಒಟ್ಟುಗೂಡಿಸಲಾಗುತ್ತದೆ. ಇದನ್ನು ಹೀಗೆ ಮಾಡಬಹುದುಃ .. ಹಂತ 3. ಎಲ್ಪಿಯನ್ನು ನಿರ್ಮಿಸುವುದು ಮತ್ತು ಪರಿಹಾರವನ್ನು ಪೂರ್ಣಗೊಳಿಸುವುದು ನಾವು ಸಮಗ್ರತೆಯ ನಿರ್ಬಂಧಗಳಿಲ್ಲದೆ ಸಂರಚನೆಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಪರಿಗಣಿಸುತ್ತೇವೆಃ ಇಲ್ಲಿ, ಪ್ರತಿ ಸಂರಚನೆಯ ಭಾಗಶಃ ಸಂಖ್ಯೆಯನ್ನು ಬಳಸಲು ನಮಗೆ ಅವಕಾಶವಿದೆ. ಉದಾಹರಣೆಃ 3 ಗಾತ್ರದ 31 ವಸ್ತುಗಳು ಮತ್ತು 4 ಗಾತ್ರದ 7 ವಸ್ತುಗಳು ಇವೆ ಎಂದು ಭಾವಿಸೋಣ, ಮತ್ತು ಬಿನ್-ಗಾತ್ರವು 10 ಆಗಿದೆ. ಸಂರಚನೆಗಳು ಹೀಗಿವೆಃ 4,44,34,334,33,333. ನಿರ್ಬಂಧಗಳು [0,0,1,2,1,2,3] * x = 31 ಮತ್ತು [1,2,1,1,0,0,0] * x = 7. ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್ಪಿಗೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರವೆಂದರೆ [0,0,0,7,0,0,17/3] ಅಂದರೆಃ 334 ಸಂರಚನೆಯ 7 ತೊಟ್ಟಿಗಳು ಮತ್ತು 333 ಸಂರಚನೆಯ 17/3 ತೊಟ್ಟಿಗಳಿವೆ. ಎರಡು ವಿಭಿನ್ನ ಸಂರಚನೆಗಳು ಮಾತ್ರ ಬೇಕಾಗುತ್ತವೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಎಲ್. ಓ. ಪಿ. ಟಿ. ಯಿಂದ ರೇಖೀಯ ಕಾರ್ಯಕ್ರಮದ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವನ್ನು ಸೂಚಿಸಿ. ಈ ಕೆಳಗಿನ ಸಂಬಂಧಗಳು ಸ್ಪಷ್ಟವಾಗಿವೆಃ ಎಫ್. ಓ. ಪಿ. ಟಿ. (ಐ) ≤ ಎಲ್. ಓ. ಪಿ. ಟಿ. (ಐ), ಏಕೆಂದರೆ ಎಫ್. ಓ. ಪಿ. ಟಿ. (ಐ) ಎಂಬುದು ಎಲ್ಲಾ ತೊಟ್ಟಿಗಳನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ವಸ್ತುಗಳು ಅಥವಾ ಅಂಶಗಳಿಂದ ತುಂಬಿದಾಗ (ಬಹುಶಃ ಭಾಗಶಃ) ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯಾಗಿರುತ್ತದೆ. ಸ್ಪಷ್ಟವಾಗಿ, ಯಾವುದೇ ಪರಿಹಾರವು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿರುವುದಿಲ್ಲ. ಎಲ್ಓಪಿಟಿ (ಐ) ≤ ಒಪಿಟಿ (ಐ), ಏಕೆಂದರೆ ಎಲ್ಓಪಿಟಿ (ಐ) ಕಡಿಮೆ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಕನಿಷ್ಠಗೊಳಿಸುವ ಸಮಸ್ಯೆಗೆ ಪರಿಹಾರವಾಗಿದೆ. ಒಪಿಟಿ (ಐ) <2 * ಎಫ್ಒಪಿಟಿ (ಐ), ಕನಿಷ್ಠ 2 * ಎಫ್ಒಪಿಟಿ (ಐ) ತೊಟ್ಟಿಗಳನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿ, ಎರಡು ಕನಿಷ್ಠ ತುಂಬಿದ ತೊಟ್ಟಿಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಬಿ ಆಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಅವುಗಳನ್ನು ಒಂದೇ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಸಂಯೋಜಿಸಬಹುದು. ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್ಪಿಗೆ ಪರಿಹಾರವನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಅವಿಭಾಜ್ಯ ಪರಿಹಾರಕ್ಕೆ ಪೂರ್ಣಗೊಳಿಸಬಹುದು. ನಾವು ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್ಪಿಗೆ x ಪರಿಹಾರವನ್ನು ಹೊಂದಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣ. ನಾವು ಈ ಕೆಳಗಿನಂತೆ ಅವಿಭಾಜ್ಯ ಐಎಲ್ಪಿಗೆ x ಅನ್ನು ಪರಿಹಾರವಾಗಿ ಸುತ್ತಿಕೊಳ್ಳುತ್ತೇವೆ. x ಎಂಬುದು ಫ್ರ್ಯಾಕ್ಷನಲ್ LP ಯ ಅತ್ಯುತ್ತಮವಾದ ಮೂಲ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರವಾಗಿರಲಿ. ಅದನ್ನು ತೊಟ್ಟಿಗಳೆಂದು ಭಾವಿಸೋಣ (ಅದು ಭಾಗಶಃ ಸಂಖ್ಯೆಯಾಗಿರಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ). ಫ್ರ್ಯಾಕ್ಷನಲ್ LP ಯು m ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿರುವುದರಿಂದ (ಪ್ರತಿ ವಿಭಿನ್ನ ಗಾತ್ರಕ್ಕೆ ಒಂದು), x ಗರಿಷ್ಠ m ನಾನ್ಜೀರೋ ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಅಂದರೆ, ಗರಿಷ್ಠ m ವಿಭಿನ್ನ ಸಂರಚನೆಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ನಾವು x ನಿಂದ ಪ್ರಧಾನ ಭಾಗ ಮತ್ತು ಉಳಿದ ಭಾಗವನ್ನು ಒಳಗೊಂಡಿರುವ ಅವಿಭಾಜ್ಯ ಪ್ಯಾಕಿಂಗ್ ಅನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆ. ಮುಖ್ಯ ಭಾಗವು ಪ್ರತಿ ಸಂರಚನೆ ಸಿ ಯ ನೆಲದ (xc) ತೊಟ್ಟಿಗಳನ್ನು ಹೊಂದಿದೆ, ಇದಕ್ಕಾಗಿ xc> 0 ಆಗಿದೆ. ಉಳಿದ ಭಾಗಕ್ಕೆ (ಆರ್ ನಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ), ನಾವು ಎರಡು ಕ್ಯಾಂಡಿಡೇಟ್ ಪ್ಯಾಕಿಂಗ್ಗಳನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆಃ ಪ್ರತಿ ಕಾನ್ಫಿಗರೇಶನ್ ಸಿ ಯ ಒಂದೇ ಬಿನ್, ಇದಕ್ಕಾಗಿ xc> 0; ಎಲ್ಲಾ ಎಂ ಬಿನ್ಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. 2 * ಎಫ್. ಓ. ಪಿ. ಟಿ. (ಆರ್) ತೊಟ್ಟಿಗಳಿಗಿಂತ ಕಡಿಮೆ ಇರುವ ದುರಾಸೆಯ ಪ್ಯಾಕಿಂಗ್ (ಕನಿಷ್ಠ 2 * ಎಫ್. ಓ. ಪಿ. ಟಿ. (ಆರ್) ತೊಟ್ಟಿಗಳಿದ್ದರೆ, ಎರಡು ಚಿಕ್ಕ ತೊಟ್ಟಿಗಳನ್ನು ಸಂಯೋಜಿಸಬಹುದು). ಈ ಪ್ಯಾಕೇಜಿಂಗ್ಗಳಲ್ಲಿ ಚಿಕ್ಕದಕ್ಕೆ ಕನಿಷ್ಠ (m, 2 * FOPT (R)) ≤ ಸರಾಸರಿ (m, 2 * FOPT (R)) = FOPT (R) + m/2 ಅಗತ್ಯವಿದೆ. ಇದರ ಜೊತೆಗೆ ಮುಖ್ಯ ಭಾಗದ ದುಂಡಾದ ತೊಟ್ಟಿಗಳು ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಇಳುವರಿಯನ್ನು ನೀಡುತ್ತವೆ. ಈ ಪರಿವರ್ತನೆ ಅಲ್ಗಾರಿದಮ್ನ ಕಾರ್ಯಗತಗೊಳಿಸುವ ಸಮಯವು ಓ (ಎನ್ ಲಾಗ್ ಎನ್) ಆಗಿದೆ. ಇದು ಅದನ್ನೂ ಸೂಚಿಸುತ್ತದೆ. ಹಂತ 4. ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್. ಪಿ. ಯನ್ನು ಪರಿಹರಿಸುವುದು ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್. ಪಿ. ಯನ್ನು ಪರಿಹರಿಸುವಲ್ಲಿ ಮುಖ್ಯ ಸವಾಲೆಂದರೆ ಅದು ದೊಡ್ಡ ಸಂಖ್ಯೆಯ ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರಬಹುದು-ಪ್ರತಿ ಸಂಭವನೀಯ ಸಂರಚನೆಗೆ ಒಂದು ಅಸ್ಥಿರ. ಡ್ಯುಯಲ್ ಎಲ್ಪಿ ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್ಪಿಯ ಡ್ಯುಯಲ್ ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಂ ಹೀಗಿದೆಃ ಇದು ಎಂ ವೇರಿಯೇಬಲ್ಗಳನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು ಸಿ ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿದೆ-ಇದು ಪ್ರತಿ ಸಂರಚನೆಗೆ ನಿರ್ಬಂಧವಾಗಿದೆ. ಇದು ಈ ಕೆಳಗಿನ ಆರ್ಥಿಕ ವ್ಯಾಖ್ಯಾನವನ್ನು ಹೊಂದಿದೆ. ಪ್ರತಿ ಗಾತ್ರಕ್ಕೆ, ನಾವು ಋಣಾತ್ಮಕವಲ್ಲದ ಬೆಲೆಯನ್ನು ನಿರ್ಧರಿಸಬೇಕು. ನಮ್ಮ ಲಾಭವು ಎಲ್ಲಾ ವಸ್ತುಗಳ ಒಟ್ಟು ಬೆಲೆಯಾಗಿದೆ. ಪ್ರತಿ ಸಂರಚನೆಯಲ್ಲಿನ ವಸ್ತುಗಳ ಒಟ್ಟು ಬೆಲೆ ಗರಿಷ್ಠ 1 ಆಗಿರುತ್ತದೆ ಎಂಬ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟು ನಾವು ಲಾಭವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು ಬಯಸುತ್ತೇವೆ. ಈ ಎಲ್ಪಿ ಈಗ ಕೇವಲ m ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿದೆ, ಆದರೆ ದೊಡ್ಡ ಸಂಖ್ಯೆಯ ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿದೆ. ಎಲ್ಲಾ ನಿರ್ಬಂಧಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡುವುದು ಸಹ ಅಸಾಧ್ಯವಾಗಿದೆ. ಅದೃಷ್ಟವಶಾತ್, ಎಲ್ಲಾ ನಿರ್ಬಂಧಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡದೆ, ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನದ ರೂಪಾಂತರವನ್ನು ಬಳಸಿಕೊಂಡು ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ನಿಖರತೆಯವರೆಗೆ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಸಾಧ್ಯವಿದೆ. ಈ ರೂಪಾಂತರವು ಇನ್ಪುಟ್ ಆಗಿ, ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ ಅನ್ನು ಪಡೆಯುತ್ತದೆಃ ವೆಕ್ಟರ್ y ≤ 0 ಅನ್ನು ನೀಡಿದಾಗ, ಈ ಕೆಳಗಿನ ಎರಡು ಆಯ್ಕೆಗಳಲ್ಲಿ ಒಂದನ್ನು ಹಿಂದಿರುಗಿಸುವ ಕಾರ್ಯಃ y ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆ ಎಂದು ದೃಢೀಕರಿಸಿ, ಅಂದರೆ,; ಅಥವಾ-y ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲ ಎಂದು ದೃಢೀಕರಿಸಿ, ಮತ್ತು ಉಲ್ಲಂಘಿಸಿದ ನಿರ್ದಿಷ್ಟ ನಿರ್ಬಂಧವನ್ನು ಹಿಂದಿರುಗಿಸಿ, ಅಂದರೆ, ವೆಕ್ಟರ್ a. ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನವು ದೊಡ್ಡ ಎಲಿಪ್ಸೋಯಿಡ್ನಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ, ಇದು ಸಂಪೂರ್ಣ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಡೊಮೇನ್ ಅನ್ನು ಒಳಗೊಂಡಿದೆ. ಪ್ರತಿ ಹಂತ ಟಿ ಯಲ್ಲಿ, ಇದು ಪ್ರಸ್ತುತ ದೀರ್ಘವೃತ್ತದ ಕೇಂದ್ರವನ್ನು ತೆಗೆದುಕೊಂಡು ಅದನ್ನು ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ಗೆ ಕಳುಹಿಸುತ್ತದೆಃ ಒರಾಕಲ್ ಅದು ಕಾರ್ಯಸಾಧ್ಯವೆಂದು ಹೇಳಿದರೆ, ನಾವು "ಆಪ್ಟಿಮಾಲಿಟಿ ಕಟ್" ಅನ್ನು ಮಾಡುತ್ತೇವೆಃ ನಾವು ದೀರ್ಘವೃತ್ತದಿಂದ ಎಲ್ಲಾ ಬಿಂದುಗಳನ್ನು ಕತ್ತರಿಸುತ್ತೇವೆ. ಈ ಅಂಶಗಳು ಖಂಡಿತವಾಗಿಯೂ ಸೂಕ್ತವಲ್ಲ. ಒರಾಕಲ್ ಅದು ಅಸಾಧ್ಯವೆಂದು ಹೇಳಿದರೆ ಮತ್ತು ನಿರ್ಬಂಧವನ್ನು ಉಲ್ಲಂಘಿಸಿದರೆ, ನಾವು "ಕಾರ್ಯಸಾಧ್ಯತೆ ಕಡಿತ" ವನ್ನು ಮಾಡುತ್ತೇವೆಃ ನಾವು ದೀರ್ಘವೃತ್ತದಿಂದ ಎಲ್ಲಾ ಬಿಂದುಗಳನ್ನು ಕಡಿತಗೊಳಿಸುತ್ತೇವೆ. ಈ ಅಂಶಗಳು ಖಂಡಿತವಾಗಿಯೂ ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲ. ಕತ್ತರಿಸಿದ ನಂತರ, ನಾವು ಹೊಸ, ಸಣ್ಣ ಅಂಡಾಕಾರವನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆ. ಈ ಪ್ರಕ್ರಿಯೆಯು ಸಮಯದ ಬಹುಪದದಲ್ಲಿ ಅಗತ್ಯವಾದ ನಿಖರತೆಯಲ್ಲಿ ಅಂದಾಜು ಪರಿಹಾರವಾಗಿ ಒಮ್ಮುಖವಾಗುತ್ತದೆ ಎಂದು ತೋರಿಸಬಹುದು. ಡ್ಯುಯಲ್ ಎಲ್ಪಿಗೆ ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ ನಮಗೆ ಕೆಲವು m ಋಣಾತ್ಮಕವಲ್ಲದ ಸಂಖ್ಯೆಗಳನ್ನು ನೀಡಲಾಗಿದೆ. ನಾವು ಈ ಕೆಳಗಿನ ಎರಡು ಆಯ್ಕೆಗಳ ನಡುವೆ ನಿರ್ಧರಿಸಬೇಕುಃ ಪ್ರತಿ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಸಂರಚನೆಗೆ, ಈ ಸಂರಚನೆಗೆ ಅನುಗುಣವಾದ ಮೊತ್ತವು ಗರಿಷ್ಠ 1 ಆಗಿರುತ್ತದೆ; ಇದರರ್ಥ y ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆ. ಒಂದು ಕಾರ್ಯಸಾಧ್ಯವಾದ ಸಂರಚನೆಯು ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಇದಕ್ಕಾಗಿ ಮೊತ್ತವು 1 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದೆ; ಇದರರ್ಥ y ಅಸಾಧ್ಯವಾಗಿದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಸಂರಚನೆಯನ್ನು ಸಹ ಹಿಂದಿರುಗಿಸಬೇಕು. ಈ ಸಮಸ್ಯೆಯನ್ನು ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಕ ಪರಿಹರಿಸಬಹುದು, ಅಲ್ಲಿ ವಸ್ತುವಿನ ಮೌಲ್ಯಗಳು, ವಸ್ತುವಿನ ತೂಕ ಮತ್ತು ತೂಕದ ಸಾಮರ್ಥ್ಯವು ಬಿ (ಬಿನ್ ಗಾತ್ರ) ಆಗಿರುತ್ತದೆ. ಆಪ್ಟಿಮಲ್ ನಾಪ್ಸ್ಯಾಕ್ ದ್ರಾವಣದ ಒಟ್ಟು ಮೌಲ್ಯವು ಗರಿಷ್ಠ 1 ಆಗಿದ್ದರೆ, y ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆ ಎಂದು ನಾವು ಹೇಳುತ್ತೇವೆ. ಆಪ್ಟಿಮಲ್ ನಾಪ್ಸ್ಯಾಕ್ ದ್ರಾವಣದ ಒಟ್ಟು ಮೌಲ್ಯವು 1 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ, ನಾವು y ಅನ್ನು ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲ ಎಂದು ಹೇಳುತ್ತೇವೆ ಮತ್ತು ಆಪ್ಟಿಮಲ್ ನಾಪ್ಸ್ಯಾಕ್ ದ್ರಾವಣದಲ್ಲಿರುವ ವಸ್ತುಗಳು ನಿರ್ಬಂಧವನ್ನು ಉಲ್ಲಂಘಿಸುವ ಸಂರಚನೆಗೆ ಅನುಗುಣವಾಗಿರುತ್ತವೆ (ಏಕೆಂದರೆ ಈ ಸಂರಚನೆಗೆ ಅನುಗುಣವಾದ ವೆಕ್ಟರ್ a ಗೆ). ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯನ್ನು ಸೂಡೋ-ಪಾಲಿನೋಮಿಯಲ್ ಸಮಯದಲ್ಲಿ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಮೂಲಕ ಪರಿಹರಿಸಬಹುದುಃ, ಇಲ್ಲಿ m ಎಂಬುದು ಇನ್ಪುಟ್ಗಳ ಸಂಖ್ಯೆ ಮತ್ತು V ಎಂಬುದು ವಿಭಿನ್ನ ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳ ಸಂಖ್ಯೆ. ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಯನ್ನು ಪಡೆಯಲು, ಇನ್ಪುಟ್ ರೌಂಡಿಂಗ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯನ್ನು ಸರಿಸುಮಾರು ಪರಿಹರಿಸಬಹುದು. ನಾವು ಸಹಿಷ್ಣುತೆಯಿಂದ ಪರಿಹಾರವನ್ನು ಬಯಸುತ್ತೇವೆ ಎಂದು ಭಾವಿಸೋಣ. ನಾವು ಪ್ರತಿಯೊಂದನ್ನೂ/n ನ ಹತ್ತಿರದ ಗುಣಾಕಾರಕ್ಕೆ ಸುತ್ತಿಕೊಳ್ಳಬಹುದು. ನಂತರ, 0 ಮತ್ತು 1 ರ ನಡುವಿನ ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳ ಸಂಖ್ಯೆ n/, ಮತ್ತು ರನ್-ಟೈಮ್ ಆಗಿದೆ. ಪರಿಹಾರವು ಕನಿಷ್ಠ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರ ಮೈನಸ್/ಎನ್ ಆಗಿದೆ. ಅಂದಾಜು ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ನೊಂದಿಗೆ ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನ ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನವನ್ನು ಅಂದಾಜು ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ ಅನ್ನು ಬಳಸಲು ಅಳವಡಿಸಿಕೊಳ್ಳಬೇಕು. ಪ್ರಸ್ತುತ ದೀರ್ಘವೃತ್ತಾಕಾರದ ಕೇಂದ್ರವನ್ನು ಗಮನಿಸಿದರೆಃ ಅಂದಾಜು ಒರಾಕಲ್ 1 ಕ್ಕಿಂತ ದೊಡ್ಡ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಪರಿಹಾರವನ್ನು ಹಿಂದಿರುಗಿಸಿದರೆ, ಅದು ಖಂಡಿತವಾಗಿಯೂ ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲ, ಮತ್ತು ಪರಿಹಾರವು ನಿರ್ಬಂಧ a ಅನ್ನು ಉಲ್ಲಂಘಿಸುವ ಸಂರಚನೆಗೆ ಅನುಗುಣವಾಗಿರುತ್ತದೆ. ನಾವು "ಕಾರ್ಯಸಾಧ್ಯತೆಯನ್ನು ಕಡಿತಗೊಳಿಸುತ್ತೇವೆ", ದೀರ್ಘವೃತ್ತಾಕಾರದ ಎಲ್ಲಾ ಬಿಂದುಗಳನ್ನು y ಗೆ ಕಡಿತಗೊಳಿಸುತ್ತೇವೆ. ಅಂದಾಜು ಒರಾಕಲ್ ಗರಿಷ್ಠ 1 ಮೌಲ್ಯದೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಹಿಂದಿರುಗಿಸಿದರೆ, ಅದು ಕಾರ್ಯಸಾಧ್ಯವಾಗಬಹುದು ಅಥವಾ ಇಲ್ಲದಿರಬಹುದು, ಆದರೆ ದುಂಡಾಗಿಸುವುದು (ಅದನ್ನು ಸೂಚಿಸುತ್ತದೆ) ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆ. ರೌಂಡಿಂಗ್ ವ್ಯಾಖ್ಯಾನದ ಪ್ರಕಾರ, ನಮಗೆ ಅದು ತಿಳಿದಿದೆ. ನಾವು ಇನ್ನೂ "ಆಪ್ಟಿಮಾಲಿಟಿ ಕಟ್" ಅನ್ನು ಮಾಡುತ್ತೇವೆಃ ನಾವು ದೀರ್ಘವೃತ್ತದಿಂದ ಎಲ್ಲಾ ಬಿಂದುಗಳನ್ನು y ಗೆ ಕತ್ತರಿಸುತ್ತೇವೆ. ಇದು ಅಸಾಧ್ಯವಾಗಿರಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಆದ್ದರಿಂದ ಅದರ ಮೌಲ್ಯವು ಒಪಿಟಿಗಿಂತ ದೊಡ್ಡದಾಗಿರಬಹುದು. ಆದ್ದರಿಂದ, ಸೂಕ್ತವಾದ ಉದ್ದೇಶವನ್ನು ಹೊಂದಿರುವ ಕೆಲವು ಅಂಶಗಳನ್ನು ನಾವು ತೆಗೆದುಹಾಕಬಹುದು. ಆದಾಗ್ಯೂ, ತೆಗೆದುಹಾಕಲಾದ ಬಿಂದುಗಳು ತೃಪ್ತಿಪಡಿಸುತ್ತವೆ; ಅದರ ಮೌಲ್ಯವು ಮೌಲ್ಯಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ ಯಾವುದೇ ಬಿಂದುವನ್ನು ತೆಗೆದುಹಾಕಲಾಗುವುದಿಲ್ಲ. ಅಂದಾಜು ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ ಅನ್ನು ಬಳಸುವುದು ಡ್ಯುಯಲ್ ಎಲ್ಪಿಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರವನ್ನು ನೀಡುತ್ತದೆ, ಹೆಚ್ಚಿನ ಪುನರಾವರ್ತನೆಗಳ ನಂತರ, ಅಲ್ಲಿ. ಅಂದಾಜು ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ನೊಂದಿಗೆ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನದ ಒಟ್ಟು ರನ್-ಟೈಮ್ ಆಗಿದೆ. ನಿರ್ಬಂಧಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದು ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನದ ಸಮಯದಲ್ಲಿ, ನಾವು ರೂಪದ ಗರಿಷ್ಠ ಕ್ಯೂ ನಿರ್ಬಂಧಗಳನ್ನು ಬಳಸುತ್ತೇವೆ. ಎಲ್ಲಾ ಇತರ ನಿರ್ಬಂಧಗಳನ್ನು ತೆಗೆದುಹಾಕಬಹುದು, ಏಕೆಂದರೆ ಅವು ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನದ y * ಫಲಿತಾಂಶದ ಮೇಲೆ ಯಾವುದೇ ಪರಿಣಾಮ ಬೀರುವುದಿಲ್ಲ. ನಾವು ಇನ್ನೂ ಹೆಚ್ಚಿನ ನಿರ್ಬಂಧಗಳನ್ನು ತೆಗೆದುಹಾಕಬಹುದು. m ವೇರಿಯೇಬಲ್ಗಳಿರುವ ಯಾವುದೇ LPಯಲ್ಲಿ, ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ನಿರ್ಧರಿಸಲು ಸಾಕಾಗುವ m ನಿರ್ಬಂಧಗಳ ಒಂದು ಸೆಟ್ ಇರುತ್ತದೆ ಎಂದು ತಿಳಿದಿದೆ (ಅಂದರೆ, ಈ m ನಿರ್ಬಂಧಗಳನ್ನು ಮಾತ್ರ ಬಳಸಿದರೂ ಸಹ ಸೂಕ್ತವಾದ ಮೌಲ್ಯವು ಒಂದೇ ಆಗಿರುತ್ತದೆ). ನಾವು ಮೇಲಿನಂತೆ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನವನ್ನು ಪದೇ ಪದೇ ಚಲಾಯಿಸಬಹುದು, ಪ್ರತಿ ಬಾರಿಯೂ ನಿರ್ದಿಷ್ಟ ನಿರ್ಬಂಧಗಳನ್ನು ತೆಗೆದುಹಾಕಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಪರಿಣಾಮವಾಗಿ ಉಂಟಾಗುವ ದೋಷವು ಗರಿಷ್ಠವಾಗಿದ್ದರೆ, ನಾವು ಈ ನಿರ್ಬಂಧಗಳನ್ನು ಶಾಶ್ವತವಾಗಿ ತೆಗೆದುಹಾಕುತ್ತೇವೆ. ನಮಗೆ ಹೆಚ್ಚಿನ ಎಲಿಮಿನೇಷನ್ಗಳ ಅಗತ್ಯವಿದೆ ಎಂದು ತೋರಿಸಬಹುದು, ಆದ್ದರಿಂದ ಶೇಖರಣೆಯ ದೋಷವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ನಾವು ನಿರ್ಬಂಧಗಳ ಸೆಟ್ಗಳನ್ನು ನಿರ್ಣಾಯಕವಾಗಿ ಪ್ರಯತ್ನಿಸಿದರೆ, ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ಎಂ ಪ್ರಯೋಗಗಳಲ್ಲಿ ಒಂದು ಯಶಸ್ವಿಯಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ನಾವು ಹೆಚ್ಚಿನ ಸಮಯಗಳಲ್ಲಿ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನವನ್ನು ಬಳಸಬೇಕಾಗುತ್ತದೆ. ಯಾದೃಚ್ಛಿಕವಾಗಿ ತೆಗೆದುಹಾಕಲು ನಾವು ನಿರ್ಬಂಧಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡಿದರೆ, ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯ ಪುನರಾವರ್ತನೆಗಳು. ಅಂತಿಮವಾಗಿ, ನಾವು ಕೇವಲ m ವೇರಿಯೇಬಲ್ಗಳು ಮತ್ತು m ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಕಡಿಮೆಗೊಳಿಸಲಾದ ಡ್ಯುಯಲ್ LPಯನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಕಡಿಮೆಯಾದ ಎಲ್. ಪಿ. ಯ ಅತ್ಯುತ್ತಮ ಮೌಲ್ಯವು ಕನಿಷ್ಠ ಎಲ್ಲಿದೆ. ಪ್ರೈಮಲ್ ಎಲ್ಪಿಯನ್ನು ಪರಿಹರಿಸುವುದು ಎಲ್ಪಿ ಡ್ಯುಯಾಲಿಟಿ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪ್ರೈಮಲ್ ಎಲ್ಪಿಯ ಕನಿಷ್ಠ ಮೌಲ್ಯವು ಡ್ಯುಯಲ್ ಎಲ್ಪಿಯ ಗರಿಷ್ಠ ಮೌಲ್ಯಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ, ಇದನ್ನು ನಾವು ಎಲ್ಒಪಿಟಿ ಯಿಂದ ಸೂಚಿಸುತ್ತೇವೆ. ಒಮ್ಮೆ ನಾವು ರಿಡ್ಯೂಸ್ಡ್ ಡ್ಯುಯಲ್ ಎಲ್ಪಿ ಹೊಂದಿದ್ದರೆ, ನಾವು ಅದರ ಡ್ಯುಯಲ್ ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ರಿಡ್ಯೂಸ್ಡ್ ಪ್ರೈಮಲ್ ಎಲ್ಪಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ. ಈ ಎಲ್ಪಿ ಕೇವಲ m ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿದೆ-ಇದು ಸಿ ಸಂರಚನೆಗಳ ಹೊರಗೆ ಕೇವಲ m ಗೆ ಅನುಗುಣವಾಗಿರುತ್ತದೆ. ಕಡಿಮೆಯಾದ ಡ್ಯುಯಲ್ ಎಲ್ಪಿಯ ಗರಿಷ್ಠ ಮೌಲ್ಯವು ಕನಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಕಡಿಮೆಯಾದ ಪ್ರೈಮಲ್ ಎಲ್ಪಿಯ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವು ಗರಿಷ್ಠವಾಗಿದೆ ಎಂದು ತೋರಿಸಬಹುದು. ಈ ದ್ರಾವಣವು ಗರಿಷ್ಠ m ಸಂರಚನೆಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಅತ್ಯುತ್ತಮವಾದ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಅನ್ನು ನೀಡುತ್ತದೆ. ಎಲ್ಲಾ ಐಟಂಗಳು ಇದಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ, ನಿರ್ಣಾಯಕ ಅಲ್ಗಾರಿದಮ್ನ ಒಟ್ಟು ರನ್-ಟೈಮ್ ಹೀಗಿರುತ್ತದೆಃ ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ನ ನಿರೀಕ್ಷಿತ ಒಟ್ಟು ರನ್-ಟೈಮ್ ಹೀಗಿರುತ್ತದೆಃ ಎಂಡ್-ಟು-ಎಂಡ್ ಕ್ರಮಾವಳಿಗಳಾದ ಕರ್ಮಾರ್ಕರ್ ಮತ್ತು ಕಾರ್ಪ್ ಮೂರು ಕ್ರಮಾವಳಿಗಳನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು, ಅವು ಮೇಲಿನ ತಂತ್ರಗಳನ್ನು ವಿಭಿನ್ನ ನಿಯತಾಂಕಗಳೊಂದಿಗೆ ಬಳಸುತ್ತವೆ. ಈ ಎಲ್ಲಾ ಕ್ರಮಾವಳಿಗಳ ರನ್-ಟೈಮ್ ಒಂದು ಕಾರ್ಯವನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ, ಇದು ಬಹುಪದ ಕಾರ್ಯವಾಗಿದ್ದು, ಸಹಿಷ್ಣುತೆ h = 1 ರೊಂದಿಗೆ ಫ್ರ್ಯಾಕ್ಷನಲ್ LP ಅನ್ನು ಪರಿಹರಿಸಲು ತೆಗೆದುಕೊಳ್ಳುವ ಸಮಯವನ್ನು ವಿವರಿಸುತ್ತದೆ, ಅಂದರೆ, ನಿರ್ಣಾಯಕ ಆವೃತ್ತಿಗೆ. ಕ್ರಮಾವಳಿ 1 ಅಪೇಕ್ಷಿತ ಅಂದಾಜು ನಿಖರತೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಸ್ಥಿರಾಂಕವಾಗಿರಲಿ. 1-ಎ. ಸೆಟ್ ಮಾಡಿ. g. 2-a ಗಿಂತ ಚಿಕ್ಕದಾದ ಎಲ್ಲಾ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ನಿರ್ಮಿಸಲಾದ ಒಂದು ಉದಾಹರಣೆಯಾಗಿರಲಿ. ಸೆಟ್ ಮಾಡಿ. k ನಿಯತಾಂಕದೊಂದಿಗೆ ರೇಖೀಯ ಗುಂಪಿನಿಂದ ನಿರ್ಮಿಸಲಾದ ಒಂದು ಉದಾಹರಣೆಯಾಗಿರಲಿ, ಮತ್ತು ಉಳಿದ ಉದಾಹರಣೆಯಾಗಿರಲಿ (k ದೊಡ್ಡ ವಸ್ತುಗಳ ಗುಂಪು). ಅದನ್ನು ಗಮನಿಸಿ. 3-ಎ. ಸಮಗ್ರತೆಯ ನಿರ್ಬಂಧಗಳಿಲ್ಲದೆ ಸಂರಚನೆಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ರಚಿಸಿ. 4. ಸಹಿಷ್ಣುತೆ h = 1 ಹೊಂದಿರುವ x ಪರಿಹಾರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಇದರ ಫಲಿತಾಂಶವೆಂದರೆ ಡಬ್ಬಿಗಳೊಂದಿಗೆ ಫ್ರ್ಯಾಕ್ಷನಲ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ. ರನ್-ಟೈಮ್ ಆಗಿದೆ. 3-ಬಿ. ಒಂದು ಅವಿಭಾಜ್ಯ ಪರಿಹಾರಕ್ಕೆ x ಅನ್ನು ಸುತ್ತಿಕೊಳ್ಳಿ. ಭಾಗಶಃ ಭಾಗಕ್ಕೆ ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳನ್ನು ಸೇರಿಸಿ. ತೊಟ್ಟಿಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆ. 2-ಬಿ. ಹೆಚ್ಚಿನ ಕೆ ಡಬ್ಬಿಗಳಲ್ಲಿ ವಸ್ತುಗಳನ್ನು ಪ್ಯಾಕ್ ಮಾಡಿ; ಒಂದು ಪ್ಯಾಕಿಂಗ್ ಅನ್ನು ಪಡೆಯಿರಿ. ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ. 1-ಬಿ. ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು ಜಿ ಗಿಂತ ಚಿಕ್ಕದಾದ ವಸ್ತುಗಳನ್ನು ಸೇರಿಸಿ. ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ ಹೀಗಿದೆಃ ಒಟ್ಟಾರೆಯಾಗಿ, ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ ಇದೆ ಮತ್ತು ರನ್-ಟೈಮ್ ಇದೆ. ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ನಾವು ಪಡೆಯುತ್ತೇವೆ. ಅಲ್ಗಾರಿದಮ್ 2 ಒಂದು ನೈಜ ನಿಯತಾಂಕ ಮತ್ತು ನಂತರ ನಿರ್ಧರಿಸಬೇಕಾದ ಪೂರ್ಣಾಂಕ ನಿಯತಾಂಕವಾಗಿರಲಿ. 1-ಎ. g. 2 ಗಿಂತ ಚಿಕ್ಕದಾದ ಎಲ್ಲಾ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ನಿರ್ಮಿಸಲಾದ ಒಂದು ಉದಾಹರಣೆಯಾಗಿರಲಿ. ಮಾಡುವಾಗಃ 2-ಎ. k ನಿಯತಾಂಕದೊಂದಿಗೆ ಪರ್ಯಾಯ ಜ್ಯಾಮಿತೀಯ ಗುಂಪನ್ನು ಮಾಡಿ. ಫಲಿತಾಂಶದ ಉದಾಹರಣೆಯಾಗಿರಲಿ, ಮತ್ತು ಉಳಿದ ಉದಾಹರಣೆಯಾಗಿರಲಿ. ನಮ್ಮ ಬಳಿ ಇದೆ. 3-ಎ. ಸಮಗ್ರತೆಯ ನಿರ್ಬಂಧಗಳಿಲ್ಲದೆ ಸಂರಚನೆಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ರಚಿಸಿ. 4. ಸಹಿಷ್ಣುತೆ h = 1 ಹೊಂದಿರುವ x ಪರಿಹಾರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಇದರ ಫಲಿತಾಂಶವೆಂದರೆ ಡಬ್ಬಿಗಳೊಂದಿಗೆ ಫ್ರ್ಯಾಕ್ಷನಲ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ. ರನ್-ಟೈಮ್ ಆಗಿದೆ. 3-ಬಿ. ಒಂದು ಅವಿಭಾಜ್ಯ ಪರಿಹಾರಕ್ಕೆ x ಅನ್ನು ಸುತ್ತಿಕೊಳ್ಳಿ. ಭಾಗಶಃ ಭಾಗಕ್ಕೆ ಡಬ್ಬಿಗಳನ್ನು ಸೇರಿಸಬೇಡಿ. ಬದಲಿಗೆ, ಪ್ಯಾಕ್ ಮಾಡಲಾದ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕಿ. 2-ಬಿ. ಹೆಚ್ಚಿನ ಡಬ್ಬಿಗಳಲ್ಲಿ ವಸ್ತುಗಳನ್ನು ಪ್ಯಾಕ್ ಮಾಡಿ. 2. ಒಮ್ಮೆ, ಉಳಿದ ವಸ್ತುಗಳನ್ನು ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳಲ್ಲಿ ದುರಾಸೆಯಿಂದ ಕಟ್ಟಿಕೊಳ್ಳಿ. ಹಂತ 2 ರಲ್ಲಿ ಲೂಪ್ನ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ, x ನ ಭಾಗಶಃ ಭಾಗವು ಗರಿಷ್ಠ m (K) ಮಾದರಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲಿ ಎಫ್ಓಪಿಟಿ ಕೆ ಅಂಶದಿಂದ ಇಳಿಯುತ್ತದೆ, ಆದ್ದರಿಂದ ಪುನರಾವರ್ತನೆಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಬಳಸಿದ ತೊಟ್ಟಿಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆ ಹೀಗಿದೆಃ 1-ಬಿ. ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು ಜಿ ಗಿಂತ ಚಿಕ್ಕದಾದ ವಸ್ತುಗಳನ್ನು ಸೇರಿಸಿ. ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ ಹೀಗಿದೆಃ ರನ್-ಟೈಮ್ ಒಳಗಿದೆ. ಈಗ, ನಾವು k = 2 ಮತ್ತು g = 1/FOPT (I) ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿದರೆ, ನಾವು ಪಡೆಯುತ್ತೇವೆಃ, ಮತ್ತು ಆದ್ದರಿಂದಃ, ಆದ್ದರಿಂದ ಒಟ್ಟು ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ ಇರುತ್ತದೆ. ರನ್-ಟೈಮ್ ಆಗಿದೆ. ರನ್-ಟೈಮ್ ಅನ್ನು ನಿಖರತೆಯೊಂದಿಗೆ ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಲು ಒಂದೇ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ವಿವಿಧ ನಿಯತಾಂಕಗಳೊಂದಿಗೆ ಬಳಸಬಹುದು. ಕೆಲವು ನಿಯತಾಂಕಗಳಿಗಾಗಿ, ಮತ್ತು ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿ. ನಂತರ, ಪ್ಯಾಕಿಂಗ್ಗೆ ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳು ಬೇಕಾಗುತ್ತವೆ, ಮತ್ತು ರನ್-ಟೈಮ್ ಒಳಗಿರುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ 3 ಮೂರನೆಯ ಅಲ್ಗಾರಿದಮ್ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆ m ಚಿಕ್ಕದಾಗಿದ್ದಾಗ ಉಪಯುಕ್ತವಾಗಿದೆ (ಹೆಚ್ಚಿನ-ಮಲ್ಟಿಪ್ಲಿಸಿಟಿ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಅನ್ನು ಸಹ ನೋಡಿ). 1-ಎ. ಸೆಟ್ ಮಾಡಿ. ಜಿ ಗಿಂತ ಚಿಕ್ಕದಾದ ಎಲ್ಲಾ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ನಿರ್ಮಿಸಲಾದ ಒಂದು ಉದಾಹರಣೆಯಾಗಿರಲಿ. ಹಾಗಿದ್ದಲ್ಲಿಃ 3-ಎ. ಸಮಗ್ರತೆಯ ನಿರ್ಬಂಧಗಳಿಲ್ಲದೆ ಸಂರಚನೆಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ರಚಿಸಿ. 4. ಸಹಿಷ್ಣುತೆ h = 1 ಹೊಂದಿರುವ x ಪರಿಹಾರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಇದರ ಫಲಿತಾಂಶವೆಂದರೆ ಡಬ್ಬಿಗಳೊಂದಿಗೆ ಫ್ರ್ಯಾಕ್ಷನಲ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ. ರನ್-ಟೈಮ್ ಆಗಿದೆ. 3-ಬಿ. ಒಂದು ಅವಿಭಾಜ್ಯ ಪರಿಹಾರಕ್ಕೆ x ಅನ್ನು ಸುತ್ತಿಕೊಳ್ಳಿ. ಭಾಗಶಃ ಭಾಗಕ್ಕೆ ಡಬ್ಬಿಗಳನ್ನು ಸೇರಿಸಬೇಡಿ. ಬದಲಿಗೆ, ಪ್ಯಾಕ್ ಮಾಡಲಾದ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕಿ. ಉಳಿದ ತುಣುಕುಗಳ ಮೇಲೆ ಅಲ್ಗಾರಿದಮ್ 2ರ 2ನೇ ಹಂತವನ್ನು ಚಲಾಯಿಸಿ. 1-ಬಿ. ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು ಜಿ ಗಿಂತ ಚಿಕ್ಕದಾದ ವಸ್ತುಗಳನ್ನು ಸೇರಿಸಿ. ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆ ಹೀಗಿದೆಃ ಇದು ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಬಳಸುತ್ತದೆ, ಮತ್ತು ರನ್-ಟೈಮ್ ಒಳಗಿರುತ್ತದೆ. ಸುಧಾರಣೆಗಳು ಇನ್ನೂ ಉತ್ತಮ ಅಂದಾಜುಗಳನ್ನು ಒದಗಿಸಲು ಕೆ. ಕೆ ತಂತ್ರಗಳನ್ನು ನಂತರ ಸುಧಾರಿಸಲಾಯಿತು. ರಾಥ್ವೋಸ್ ಅಲ್ಗಾರಿದಮ್ 2 ರಂತೆಯೇ ಅದೇ ಯೋಜನೆಯನ್ನು ಬಳಸುತ್ತಾರೆ, ಆದರೆ ಹಂತ 2 ರಲ್ಲಿ ವಿಭಿನ್ನ ರೌಂಡಿಂಗ್ ಕಾರ್ಯವಿಧಾನವನ್ನು ಬಳಸುತ್ತಾರೆ. ಅವರು "ಅಂಟು" ಹಂತವನ್ನು ಪರಿಚಯಿಸಿದರು, ಇದರಲ್ಲಿ ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಒಟ್ಟಿಗೆ ಅಂಟಿಸಿ ಒಂದೇ ದೊಡ್ಡ ವಸ್ತುವನ್ನು ಪಡೆಯಲಾಗುತ್ತದೆ. ಈ ಅಂಟುವಿಕೆಯನ್ನು ಚಿಕ್ಕ ವಸ್ತುವಿನ ಗಾತ್ರವನ್ನು ಸುಮಾರು ಹೆಚ್ಚಿಸಲು ಬಳಸಬಹುದು. ಎಲ್ಲಾ ಗಾತ್ರಗಳು ಕನಿಷ್ಠವಾಗಿದ್ದಾಗ, ನಾವು ಅಲ್ಗಾರಿದಮ್ 2 ರ ಗ್ಯಾರಂಟಿಯಲ್ಲಿ ಬದಲಿಸಬಹುದು, ಮತ್ತು ಪಡೆಯಬಹುದುಃ, ಇದು ತೊಟ್ಟಿಗಳನ್ನು ನೀಡುತ್ತದೆ. ಹೋಬರ್ಗ್ ಮತ್ತು ರಾಥ್ವೋಸ್ ಇದೇ ರೀತಿಯ ಯೋಜನೆಯನ್ನು ಬಳಸುತ್ತಾರೆ, ಇದರಲ್ಲಿ ವಸ್ತುಗಳನ್ನು ಮೊದಲು "ಧಾರಕಗಳಲ್ಲಿ" ತುಂಬಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ನಂತರ ಧಾರಕಗಳನ್ನು ತೊಟ್ಟಿಗಳಲ್ಲಿ ತುಂಬಿಸಲಾಗುತ್ತದೆ. ಅವರ ಅಲ್ಗಾರಿದಮ್ಗೆ ಹೆಚ್ಚಿನ ತೊಟ್ಟಿಗಳು ಬೇಕಾಗುತ್ತವೆ. ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್