Karmarkar–Karp bin packing algorithms
કરમરકર-કાર્પ (કે. કે.) બિન પેકિંગ અલ્ગોરિધમ્સ એ બિન પેકિંગ સમસ્યા માટે કેટલાક સંબંધિત અંદાજિત અલ્ગોરિધમ છે. બિન પેકિંગની સમસ્યા એ છે કે વિવિધ કદની વસ્તુઓને સમાન ક્ષમતાના ડબ્બાઓમાં પેક કરવાની સમસ્યા છે, જેમ કે ડબ્બાઓની કુલ સંખ્યા શક્ય તેટલી ઓછી હોય છે. શ્રેષ્ઠ ઉકેલ શોધવો ગણતરીની દૃષ્ટિએ મુશ્કેલ છે. કરમરકર અને કાર્પે એક એલ્ગોરિધમ તૈયાર કર્યું જે બહુપદી સમયમાં ચાલે છે અને મોટાભાગના ડબ્બાઓ સાથે ઉકેલ શોધે છે, જ્યાં ઓ. પી. ટી. એ શ્રેષ્ઠ ઉકેલમાં ડબ્બાઓની સંખ્યા છે. તેઓએ થોડી અલગ અંદાજ બાંયધરીઓ અને રન-ટાઇમ સીમાઓ સાથે અન્ય કેટલાક અલ્ગોરિધમ્સ પણ તૈયાર કર્યા. બિન પેકિંગના અભ્યાસમાં કેકે અલ્ગોરિધમ્સને એક સફળતા માનવામાં આવી હતીઃ અગાઉ જાણીતા અલ્ગોરિધમ્સને ગુણાકાર અંદાજ મળ્યો હતો, જ્યાં કેટલાક સ્થિરાંકો માટે અથવા વધુમાં વધુ માટે ડબ્બાઓની સંખ્યા સૌથી વધુ હતી. કે. કે. અલ્ગોરિધમ્સ એ એડિટિવ અંદાજ પ્રાપ્ત કરનારા પ્રથમ હતા. બિન-પેકિંગ સમસ્યાનું ઇનપુટ એ વિવિધ કદની વસ્તુઓનો સમૂહ છે, a1,. an. નીચેના સંકેતનો ઉપયોગ થાય છેઃ n-વસ્તુઓની સંખ્યા. એમ-વિવિધ વસ્તુના કદની સંખ્યા. 1 માં દરેક i માટે, m: si એ i-th કદ છે; ni એ કદની વસ્તુઓની સંખ્યા છે. બી-બિનનું કદ. એક ઉદાહરણ I જોતાં, આપણે સૂચવીએ છીએઃ OPT (I) = ઉદાહરણ I નો શ્રેષ્ઠ ઉકેલ. FOPT (I) = (a1 +. + an)/B = સૈદ્ધાંતિક રીતે-શ્રેષ્ઠ સંખ્યામાં ડબ્બાઓ, જ્યારે તમામ ડબ્બાઓ સંપૂર્ણપણે વસ્તુઓ અથવા વસ્તુના અપૂર્ણાંકોથી ભરેલા હોય. દેખીતી રીતે, એફઓપીટી (I) ≤ ઓપીટી (I). ઉચ્ચ-સ્તરીય યોજના કેકે અલ્ગોરિધમ્સ અનિવાર્યપણે રૂપરેખાંકન રેખીય પ્રોગ્રામને હલ કરે છેઃ અહીં, એ એ m પંક્તિઓ સાથેનું મેટ્રિક્સ છે. એ નો દરેક સ્તંભ એક શક્ય રૂપરેખાંકન રજૂ કરે છે-વસ્તુ-કદનો એક બહુ-સમૂહ, જેમ કે આ તમામ કદોનો સરવાળો મહત્તમ બી હોય છે. રૂપરેખાંકનોનો સમૂહ C છે. x એ કદ C નો વેક્ટર છે. x નું દરેક તત્વ xc એ ગોઠવણી c નો ઉપયોગ કરવામાં આવે તે સંખ્યાને રજૂ કરે છે. ઉદાહરણોઃ ધારો કે વસ્તુનું કદ 3,3,3,3,3,4,4,4,4,4, અને B = 12 છે. પછી C = 10 સંભવિત રૂપરેખાંકનો છેઃ 3333; 333; 33,334,344; 4,44,444. મેટ્રિક્સ A માં બે પંક્તિઓ છેઃ s = 3 માટે [4,3,2,2,1,1,1,0,0,0] અને s = 4 માટે [0,0,0,1,0,1,2,1,2,3]. વેક્ટર n એ [5,5] છે કારણ કે દરેક કદની 5 વસ્તુઓ છે. સંભવિત શ્રેષ્ઠ ઉકેલ x = [1,0,0,0,0,0,1,0,0,1] છે, જે રૂપરેખાંકનો 3333,344,444 સાથે ત્રણ ડબ્બાનો ઉપયોગ કરવા માટે અનુરૂપ છે. આ સમસ્યાનો ઉકેલ લાવવામાં બે મુખ્ય મુશ્કેલીઓ છે. પ્રથમ, તે એક પૂર્ણાંક રેખીય પ્રોગ્રામ છે, જેને ઉકેલવા માટે ગણતરીત્મક રીતે મુશ્કેલ છે. બીજું, ચલની સંખ્યા સી છે-રૂપરેખાંકનોની સંખ્યા, જે પ્રચંડ હોઈ શકે છે. કેકે અલ્ગોરિધમ્સ ઘણી તકનીકોનો ઉપયોગ કરીને આ મુશ્કેલીઓનો સામનો કરે છે, જેમાંથી કેટલીક પહેલેથી જ ડી-લા-વેગા અને લ્યુકર દ્વારા રજૂ કરવામાં આવી હતી. અહીં અલ્ગોરિધમનું ઉચ્ચ-સ્તરનું વર્ણન છે (જ્યાં મૂળ ઉદાહરણ છે): 1-એ. ચાલો નાની વસ્તુઓને દૂર કરીને બનાવેલ એક ઉદાહરણ બનીએ. 2-એ. ચાલો વસ્તુઓને જૂથબદ્ધ કરીને અને દરેક જૂથમાં વસ્તુઓના કદને જૂથની સૌથી ઊંચી વસ્તુ સાથે ગોળાકાર કરીને એક ઉદાહરણ બનાવીએ. 3-એ. અખંડિતતાની મર્યાદાઓ વિના, માટે રૂપરેખાંકન રેખીય કાર્યક્રમની રચના કરો. 4. રિલેક્સ્ડ રેખીય પ્રોગ્રામ માટે a (અપૂર્ણાંક) ઉકેલ x ની ગણતરી કરો. 3-બી. માટે એક અભિન્ન ઉકેલ માટે x ને ગોળાકાર કરો. 2-બી. ઉકેલ મેળવવા માટે વસ્તુઓને "અન-ગ્રુપ" કરો. 1-બી. ઉકેલ મેળવવા માટે નાની વસ્તુઓ ઉમેરો. નીચે, અમે બદલામાં આ દરેક પગલાનું વર્ણન કરીએ છીએ. પગલું 1. નાની વસ્તુઓને દૂર કરવી અને ઉમેરવી નાની વસ્તુઓને દૂર કરવાની પ્રેરણા એ છે કે, જ્યારે બધી વસ્તુઓ મોટી હોય, ત્યારે દરેક ડબ્બામાં વસ્તુઓની સંખ્યા ઓછી હોવી જોઈએ, તેથી સંભવિત રૂપરેખાંકનોની સંખ્યા (પ્રમાણમાં) ઓછી હોય છે. અમે કેટલાક અચળાંક પસંદ કરીએ છીએ, અને તેના કરતા નાની તમામ વસ્તુઓને મૂળ ઉદાહરણમાંથી દૂર કરીએ છીએ. ચાલો પરિણામી ઉદાહરણ બનીએ. નોંધ લો કે દરેક ડબ્બામાં મોટાભાગની વસ્તુઓ હોઈ શકે છે. અમે પેક કરીએ છીએ અને કેટલાક ડબ્બાઓ સાથે પેકિંગ મેળવીએ છીએ. હવે, જ્યાં સુધી જગ્યા હોય ત્યાં સુધી આપણે નાની વસ્તુઓને હાલના ડબ્બામાં મનસ્વી ક્રમમાં ઉમેરીએ છીએ. જ્યારે હાલના ડબ્બામાં વધુ જગ્યા ન હોય, ત્યારે આપણે એક નવો ડબ્બો ખોલીએ છીએ (આગામી-ફિટ ડબ્બાની પેકિંગની જેમ). અંતિમ પેકિંગમાં ડબ્બાઓની સંખ્યા હોવી જોઈએ. પછીઃ સાબિતી. જો કોઈ નવા ડબ્બા ખોલવામાં નહીં આવે, તો ડબ્બાઓની સંખ્યા રહે છે. જો નવો ડબ્બો ખોલવામાં આવે, તો પછી કદાચ છેલ્લો ડબ્બો સિવાયના તમામ ડબ્બામાં ઓછામાં ઓછું કુલ કદ હોય છે, તેથી કુલ ઉદાહરણનું કદ ઓછામાં ઓછું છે. તેથી, શ્રેષ્ઠ ઉકેલ માટે ઓછામાં ઓછા ડબ્બાની જરૂર પડે છે. તો. ખાસ કરીને, g = 1/n લઈને, આપણને મળે છેઃ, ત્યારથી. તેથી, એવું માનવું સામાન્ય છે કે બધી વસ્તુઓ 1/n કરતા મોટી છે. પગલું 2. વસ્તુઓનું જૂથ બનાવવું અને બિન-જૂથ બનાવવું વસ્તુઓનું જૂથ બનાવવાની પ્રેરણા એ છે કે વિવિધ વસ્તુઓના કદની સંખ્યા ઘટાડવી, રૂપરેખાંકન એલ. પી. માં અવરોધોની સંખ્યા ઘટાડવી. સામાન્ય જૂથ બનાવવાની પ્રક્રિયા છેઃ ઘટતા કદ દ્વારા વસ્તુઓનો ઓર્ડર આપો. વસ્તુઓને જૂથોમાં વિભાજીત કરો. દરેક જૂથ માટે, જૂથની તમામ વસ્તુઓના કદને જૂથમાં સૌથી મોટા કદમાં સંશોધિત કરો. જૂથબદ્ધ કરવાની ઘણી જુદી જુદી પદ્ધતિઓ છે. લીનિયર ગ્રૂપિંગ ચાલો એક પૂર્ણાંક પરિમાણ બનીએ. જૂથ 1 માં સૌથી મોટી વસ્તુઓ મૂકો; જૂથ 2 માં આગામી સૌથી મોટી વસ્તુઓ; અને તેથી વધુ (છેલ્લા જૂથમાં વસ્તુઓ કરતાં ઓછી હોઈ શકે છે). ચાલો મૂળ ઉદાહરણ બનીએ. ચાલો પ્રથમ જૂથ (સૌથી મોટી વસ્તુઓનું જૂથ) અને પ્રથમ જૂથ વિના જૂથબદ્ધ ઉદાહરણ બનીએ. પછીઃ બધી વસ્તુઓમાં સમાન કદ હોય છે. વિવિધ કદની સંખ્યામાં છે. - કારણ કે જૂથ 1 માં જૂથ 2 માં પ્રભુત્વ ધરાવે છે (જૂથ 1 માં તમામ k વસ્તુઓ જૂથ 2 માં k વસ્તુઓ કરતા મોટી છે); તેવી જ રીતે, જૂથ 2 માં જૂથ 3 માં પ્રભુત્વ ધરાવે છે, વગેરે. - કારણ કે દરેક વસ્તુને એક જ ડબ્બામાં પેક કરવી શક્ય છે. તેથી, તા. ખરેખર, ડબ્બા સાથે ઉકેલ આપવામાં આવે તો, આપણે મોટાભાગના ડબ્બાઓ સાથે ઉકેલ મેળવી શકીએ છીએ. ભૌમિતિક વર્ગીકરણ ચાલો એક પૂર્ણાંક પરિમાણ બનીએ. ભૌમિતિક જૂથ બે તબક્કામાં આગળ વધે છેઃ ઉદાહરણને ઘણા કિસ્સાઓમાં વિભાજીત કરો જેથી, દરેક કિસ્સામાં, તમામ કદ અંતરાલમાં હોય. નોંધ લો કે, જો બધી વસ્તુઓનું કદ ઓછામાં ઓછું હોય, તો ઉદાહરણોની સંખ્યા મહત્તમ હોય છે. દરેક ઉદાહરણ પર, પરિમાણ સાથે રેખીય ગોળાકાર કરો. ચાલો પરિણામી ઉદાહરણો હોઈએ. દો અને. પછી, વિવિધ કદની સંખ્યા નીચે પ્રમાણે બંધાયેલ છેઃ બધા 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 ડબ્બા છે. નોંધ લો કે માત્ર બે અલગ અલગ રૂપરેખાંકનોની જરૂર છે. એલ. ઓ. પી. ટી. દ્વારા રેખીય કાર્યક્રમના શ્રેષ્ઠ ઉકેલને દર્શાવો. નીચેના સંબંધો સ્પષ્ટ છેઃ એફ. ઓ. પી. ટી. (I) ≤ એલ. ઓ. પી. ટી. (I), કારણ કે એફ. ઓ. પી. ટી. (I) એ ડબ્બાઓની (સંભવતઃ અપૂર્ણાંક) સંખ્યા છે જ્યારે તમામ ડબ્બા સંપૂર્ણપણે વસ્તુઓ અથવા વસ્તુઓના અપૂર્ણાંકોથી ભરેલા હોય છે. સ્પષ્ટપણે, કોઈ પણ ઉકેલ વધુ અસરકારક ન હોઈ શકે. એલ. ઓ. પી. ટી. (I) ≤ ઓ. પી. ટી. (I), કારણ કે એલ. ઓ. પી. ટી. (I) એ ઓછા અવરોધો સાથે લઘુતમ સમસ્યાનું સમાધાન છે. ઓ. પી. ટી. (I) <2 * એફ. ઓ. પી. ટી. (I), કારણ કે ઓછામાં ઓછા 2 * એફ. ઓ. પી. ટી. (I) ડબ્બાવાળા કોઈપણ પેકિંગમાં, બે ઓછામાં ઓછા ભરેલા ડબ્બાનો સરવાળો મહત્તમ બી હોય છે, તેથી તેમને એક જ ડબ્બામાં જોડી શકાય છે. અપૂર્ણાંક એલ. પી. ના ઉકેલને નીચે પ્રમાણે અભિન્ન ઉકેલમાં ગોળાકાર કરી શકાય છે. ધારો કે આપણી પાસે અપૂર્ણાંક એલ. પી. નો ઉકેલ x છે. આપણે નીચે પ્રમાણે ઇન્ટિગ્રલ આઇએલપી માટે ઉકેલમાં x ને ગોળાકાર કરીએ છીએ. ચાલો x એ અપૂર્ણાંક LP નો શ્રેષ્ઠ મૂળભૂત શક્ય ઉકેલ છે. ધારો કે તે ડબ્બા તરીકે છે (નોંધ કરો કે તે અપૂર્ણાંક સંખ્યા હોઈ શકે છે). અપૂર્ણાંક એલ. પી. માં m મર્યાદાઓ (દરેક અલગ કદ માટે એક) હોવાથી, x માં મહત્તમ m બિન-શૂન્ય ચલ હોય છે, એટલે કે, મહત્તમ m વિવિધ રૂપરેખાંકનો વપરાય છે. આપણે x થી એક અભિન્ન પેકિંગ બનાવીએ છીએ જેમાં મુખ્ય ભાગ અને શેષ ભાગ હોય છે. મુખ્ય ભાગમાં દરેક રૂપરેખાંકન c ના ફ્લોર (xc) ડબ્બા હોય છે, જેના માટે xc> 0 છે. બાકી રહેલા ભાગ (આર દ્વારા સૂચવવામાં આવે છે) માટે, આપણે બે ઉમેદવાર પેકેજિંગ બનાવીએ છીએઃ દરેક રૂપરેખાંકન c નો એક જ ડબ્બો જેના માટે xc> 0; બધા m ડબ્બામાં જરૂરી છે. લોભી પેકિંગ, જેમાં 2 * એફઓપીટી (આર) થી ઓછા ડબ્બા હોય (કારણ કે જો ત્યાં ઓછામાં ઓછા 2 * એફઓપીટી (આર) ડબ્બા હોય, તો બે સૌથી નાના ડબ્બાઓને જોડી શકાય છે). આમાંથી સૌથી નાના પેકેજિંગ માટે ન્યૂનતમ (એમ, 2 * એફઓપીટી (આર)) ≤ સરેરાશ (એમ, 2 * એફઓપીટી (આર)) = એફઓપીટી (આર) + એમ/2 જરૂરી છે. આ ઉપરાંત મુખ્ય ભાગના ગોળાકાર ડબ્બાઓ મોટા ભાગના ડબ્બાઓ પર ઉપજ આપે છે. આ રૂપાંતર અલ્ગોરિધમનો અમલ સમય ઓ (એન લોગ એન) છે. આ પણ સૂચવે છે. પગલું 4. અપૂર્ણાંક એલ. પી. ને ઉકેલવું અપૂર્ણાંક એલ. પી. ને ઉકેલવામાં મુખ્ય પડકાર એ છે કે તેમાં મોટી સંખ્યામાં ચલ હોઈ શકે છે-દરેક સંભવિત રૂપરેખાંકન માટે ચલ. દ્વિ એલ. પી. અપૂર્ણાંક એલ. પી. નો દ્વિ રેખીય કાર્યક્રમ છેઃ તેમાં m ચલ અને C અવરોધો છે-જે દરેક રૂપરેખાંકન માટે અવરોધ છે. તેમાં નીચેનું આર્થિક અર્થઘટન છે. દરેક કદ માટે, આપણે બિન-નકારાત્મક કિંમત નક્કી કરવી જોઈએ. અમારો નફો એ તમામ વસ્તુઓની કુલ કિંમત છે. અમે દરેક રૂપરેખાંકનમાં વસ્તુઓની કુલ કિંમત મહત્તમ 1 છે તે મર્યાદાઓને આધિન નફાને મહત્તમ કરવા માંગીએ છીએ. આ એલ. પી. માં હવે માત્ર m ચલ છે, પરંતુ મોટી સંખ્યામાં અવરોધો છે. તમામ અવરોધોની યાદી પણ અશક્ય છે. સદનસીબે, લંબગોળ પદ્ધતિનો એક પ્રકારનો ઉપયોગ કરીને, તમામ અવરોધોની યાદી આપ્યા વિના કોઈપણ ચોક્કસતા સુધી સમસ્યાનું સમાધાન કરવું શક્ય છે. આ વેરિઅન્ટ ઇનપુટ તરીકે મળે છે, એક સેપરેશન ઓરેકલઃ એક ફંક્શન કે જે વેક્ટર y ≤ 0 આપવામાં આવે છે, તે નીચેના બે વિકલ્પોમાંથી એક આપે છેઃ ખાતરી કરો કે y શક્ય છે, એટલે કે,; અથવા-ખાતરી કરો કે y અવ્યવહારુ છે, અને ઉલ્લંઘન થયેલ ચોક્કસ અવરોધ પરત કરે છે, એટલે કે, વેક્ટર a જેમ કે. લંબગોળ પદ્ધતિ મોટા લંબગોળ સાથે શરૂ થાય છે, જેમાં સમગ્ર શક્ય ક્ષેત્રનો સમાવેશ થાય છે. દરેક પગલું t પર, તે વર્તમાન લંબગોળનું કેન્દ્ર લે છે, અને તેને અલગ ઓરેકલમાં મોકલે છેઃ જો ઓરેકલ કહે છે કે તે શક્ય છે, તો આપણે "ઓપ્ટિમાલિટી કટ" કરીએ છીએઃ આપણે લંબગોળમાંથી તમામ બિંદુઓ y કાપીએ છીએ જેના માટે. આ બિંદુઓ ચોક્કસપણે શ્રેષ્ઠ નથી. જો ઓરેકલ કહે છે કે તે અવ્યવહારુ છે અને અવરોધ a નું ઉલ્લંઘન કરે છે, તો આપણે "શક્યતા કાપ" કરીએ છીએઃ આપણે લંબગોળમાંથી તમામ બિંદુઓ y કાપીએ છીએ જેના માટે. આ મુદ્દાઓ ચોક્કસપણે શક્ય નથી. કટ કર્યા પછી, અમે એક નવું, નાનું લંબગોળ બનાવીએ છીએ. તે દર્શાવી શકાય છે કે આ પ્રક્રિયા એક અંદાજિત ઉકેલમાં રૂપાંતરિત થાય છે, સમય બહુપદીમાં જરૂરી ચોકસાઈમાં. બેવડા એલ. પી. માટે એક અલગ ઓરેકલ આપણને કેટલાક m બિન-નકારાત્મક સંખ્યાઓ આપવામાં આવે છે. આપણે નીચેના બે વિકલ્પો વચ્ચે નિર્ણય લેવો પડશેઃ દરેક શક્ય રૂપરેખાંકન માટે, આ રૂપરેખાંકનને અનુરૂપનો સરવાળો વધુમાં વધુ 1 છે; આનો અર્થ એ છે કે y શક્ય છે. એક શક્ય રૂપરેખાંકન અસ્તિત્વમાં છે જેના માટે સરવાળો 1 કરતા મોટો છે; આનો અર્થ એ છે કે y અવ્યવહારુ છે. આ કિસ્સામાં, આપણે રૂપરેખાંકન પણ પાછું આપવું પડશે. આ સમસ્યાને નૅપસેક સમસ્યાનું સમાધાન કરીને ઉકેલી શકાય છે, જ્યાં વસ્તુના મૂલ્યો છે, વસ્તુનું વજન છે અને વજનની ક્ષમતા બી (ડબ્બાનું કદ) છે. જો ઓપ્ટિમલ નેપસેક સોલ્યુશનનું કુલ મૂલ્ય વધુમાં વધુ 1 હોય, તો આપણે કહીએ છીએ કે y શક્ય છે. જો ઓપ્ટિમલ નૅપસેક સોલ્યુશનનું કુલ મૂલ્ય 1 કરતા મોટું હોય, તો આપણે કહીએ છીએ કે y અવ્યવહારુ છે, અને ઓપ્ટિમલ નૅપસેક સોલ્યુશનમાંની વસ્તુઓ એવા રૂપરેખાંકનને અનુરૂપ છે જે બંધનું ઉલ્લંઘન કરે છે (કારણ કે વેક્ટર a માટે જે આ રૂપરેખાંકનને અનુરૂપ છે). નેપસેક સમસ્યાને સ્યુડો-બહુપદી સમયમાં ગતિશીલ પ્રોગ્રામિંગ દ્વારા ઉકેલી શકાય છેઃ, જ્યાં m એ ઇનપુટ્સની સંખ્યા છે અને V એ વિવિધ સંભવિત મૂલ્યોની સંખ્યા છે. બહુપદી-સમય અલ્ગોરિધમ મેળવવા માટે, આપણે ઇનપુટ ગોળાકારનો ઉપયોગ કરીને લગભગ નૅપસેક સમસ્યાનું સમાધાન કરી શકીએ છીએ. ધારો કે આપણે સહિષ્ણુતા સાથે ઉકેલ ઈચ્છીએ છીએ. આપણે દરેકને/n ના નજીકના ગુણાંક સુધી ગોળાકાર કરી શકીએ છીએ. પછી, 0 અને 1 વચ્ચેના સંભવિત મૂલ્યોની સંખ્યા n/છે, અને રન-ટાઇમ છે. ઉકેલ ઓછામાં ઓછો શ્રેષ્ઠ ઉકેલ માઇનસ/એન છે. અંદાજિત વિભાજન ઓરેકલ સાથે લંબગોળ પદ્ધતિ લંબગોળ પદ્ધતિને અંદાજિત વિભાજન ઓરેકલનો ઉપયોગ કરવા માટે સ્વીકારવી જોઈએ. વર્તમાન લંબગોળ કેન્દ્રને જોતાંઃ જો અંદાજિત ઓરેકલ 1 કરતા મોટા મૂલ્ય સાથે ઉકેલ આપે છે, તો તે ચોક્કસપણે અવ્યવહારુ છે, અને ઉકેલ એ રૂપરેખાંકનને અનુરૂપ છે જે અવરોધ a નું ઉલ્લંઘન કરે છે. આપણે "ફિઝિબિલિટી કટ" કરીએ છીએ, જેમાં લંબગોળને તમામ બિંદુઓ y માટે કાપીએ છીએ. જો અંદાજિત ઓરેકલ મહત્તમ 1 મૂલ્ય સાથે ઉકેલ આપે છે, તો તે શક્ય હોઈ શકે છે અથવા ન પણ હોઈ શકે, પરંતુ ગોળાકાર (તેને દ્વારા સૂચવે છે) શક્ય છે. ગોળાકારની વ્યાખ્યા મુજબ, આપણે તે જાણીએ છીએ. આપણે હજી પણ "ઓપ્ટિમાલિટી કટ" કરીએ છીએઃ આપણે લંબગોળમાંથી તમામ બિંદુઓ y કાપીએ છીએ જેના માટે. નોંધ લો કે તે અશક્ય હોઈ શકે છે, તેથી તેનું મૂલ્ય ઓ. પી. ટી. કરતા વધારે હોઈ શકે છે. તેથી, આપણે કેટલાક મુદ્દાઓને દૂર કરી શકીએ છીએ જેનો ઉદ્દેશ શ્રેષ્ઠ છે. જો કે, દૂર કરેલા બિંદુઓ સંતોષ આપે છે; જો તેનું મૂલ્ય તેના કરતાં વધુ હોય તો કોઈ બિંદુ દૂર કરવામાં આવતું નથી. અંદાજિત વિભાજન ઓરેકલનો ઉપયોગ કરીને બેવડા એલ. પી. માટે વાય * નો શક્ય ઉકેલ મળે છે, જેમાં, મોટા ભાગના પુનરાવર્તનો પછી, જ્યાં. અંદાજિત વિભાજન ઓરેકલ સાથે લંબગોળ પદ્ધતિનો કુલ રન-ટાઇમ છે. અવરોધો દૂર કરવા લંબગોળ પદ્ધતિ દરમિયાન, આપણે સ્વરૂપની મહત્તમ Q અવરોધોનો ઉપયોગ કરીએ છીએ. અન્ય તમામ અવરોધો દૂર કરી શકાય છે, કારણ કે તેઓ લંબગોળ પદ્ધતિના પરિણામ y * પર કોઈ અસર કરતા નથી. આપણે વધુ અવરોધો દૂર કરી શકીએ છીએ. તે જાણીતું છે કે, m ચલ સાથેના કોઈપણ LPમાં, m અવરોધોનો સમૂહ હોય છે જે શ્રેષ્ઠ ઉકેલ નક્કી કરવા માટે પૂરતો હોય છે (એટલે કે, શ્રેષ્ઠ મૂલ્ય એ જ હોય છે જો માત્ર આ m અવરોધોનો ઉપયોગ કરવામાં આવે તો પણ). આપણે ઉપરની જેમ લંબગોળ પદ્ધતિને વારંવાર ચલાવી શકીએ છીએ, દરેક વખતે અવરોધોનો ચોક્કસ સમૂહ દૂર કરવાનો પ્રયાસ કરી રહ્યા છીએ. જો પરિણામી ભૂલ મહત્તમ હોય, તો આપણે આ અવરોધોને કાયમી ધોરણે દૂર કરીએ છીએ. તે બતાવી શકાય છે કે આપણને મોટાભાગે નાબૂદીની જરૂર છે, તેથી સંચયની ભૂલ સૌથી વધુ છે. જો આપણે નિર્ધારીત રીતે અવરોધોનો સમૂહ અજમાવીએ, તો સૌથી ખરાબ કિસ્સામાં, m પરીક્ષણોમાંથી એક સફળ થાય છે, તેથી આપણે મોટા ભાગના સમયે લંબગોળ પદ્ધતિ ચલાવવાની જરૂર છે. જો આપણે અવ્યવસ્થિત રીતે દૂર કરવા માટે અવરોધો પસંદ કરીએ, તો પુનરાવર્તનોની અપેક્ષિત સંખ્યા છે. છેવટે, આપણી પાસે ઘટાડેલી ડ્યુઅલ એલ. પી. છે, જેમાં માત્ર m ચલ અને m અવરોધો છે. ઘટાડેલા એલ. પી. નું શ્રેષ્ઠ મૂલ્ય ઓછામાં ઓછું ક્યાં છે. પ્રાથમિક એલ. પી. ને ઉકેલવું એલ. પી. દ્વૈતતા પ્રમેય દ્વારા, પ્રાથમિક એલ. પી. નું લઘુતમ મૂલ્ય દ્વિ એલ. પી. ના મહત્તમ મૂલ્યની બરાબર હોય છે, જેને આપણે એલ. ઓ. પી. ટી. દ્વારા દર્શાવીએ છીએ. એકવાર આપણી પાસે ઘટાડેલી ડ્યુઅલ એલ. પી. હોય, ત્યારે આપણે તેની ડ્યુઅલ લઈએ છીએ, અને ઘટાડેલી પ્રાથમિક એલ. પી. લઈએ છીએ. આ એલ. પી. માં માત્ર m ચલ છે-જે C રૂપરેખાંકનોમાંથી માત્ર m ને અનુરૂપ છે. ઘટાડેલા બેવડા એલ. પી. નું મહત્તમ મૂલ્ય ઓછામાં ઓછું છે. તે દર્શાવી શકાય છે કે ઘટાડેલા પ્રાથમિક એલ. પી. નો મહત્તમ ઉકેલ છે. સોલ્યુશન મહત્તમ એમ રૂપરેખાંકનોનો ઉપયોગ કરીને લગભગ-શ્રેષ્ઠ બિન પેકિંગ આપે છે. નિર્ધારક અલ્ગોરિધમનો કુલ રન-ટાઇમ, જ્યારે બધી વસ્તુઓ તેના કરતા મોટી હોય, તે છેઃ, રેન્ડમાઇઝ્ડ અલ્ગોરિધમનો અપેક્ષિત કુલ રન-ટાઇમ છેઃ એન્ડ-ટુ-એન્ડ અલ્ગોરિધમ્સ કરમરકર અને કાર્પે ત્રણ અલ્ગોરિધમ્સ રજૂ કર્યા હતા, જે વિવિધ પરિમાણો સાથે ઉપરોક્ત તકનીકોનો ઉપયોગ કરે છે. આ તમામ અલ્ગોરિધમ્સનો રન-ટાઇમ ફંક્શન પર આધાર રાખે છે, જે બહુપદી ફંક્શન છે જે સહિષ્ણુતા h = 1 સાથે અપૂર્ણાંક LP ને ઉકેલવામાં લાગતા સમયનું વર્ણન કરે છે, જે નિર્ધારિત સંસ્કરણ માટે છે. અલ્ગોરિધમ 1 ચાલો ઇચ્છિત અંદાજની ચોકસાઈનું પ્રતિનિધિત્વ કરતો અચળાંક બનીએ. 1-એ. સેટ કરો. ચાલો ઉદાહરણ તરીકે જી. 2-એ કરતા નાની બધી વસ્તુઓને દૂર કરીને બનાવવામાં આવે છે. સેટ કરો. ચાલો k પરિમાણ સાથે રેખીય જૂથ દ્વારા બનાવવામાં આવેલ એક ઉદાહરણ હોઈએ, અને બાકીનું ઉદાહરણ (k સૌથી મોટી વસ્તુઓનું જૂથ) હોઈએ. તેની નોંધ લો. 3-એ. અખંડિતતાની મર્યાદાઓ વિના, માટે રૂપરેખાંકન રેખીય કાર્યક્રમની રચના કરો. 4. x માટે સોલ્યુશનની ગણતરી કરો, જેમાં ટોલરન્સ h = 1 છે. પરિણામ એ છે કે ડબ્બા સાથે અપૂર્ણાંક ડબ્બા પેક કરવામાં આવે છે. રન-ટાઇમ છે. 3-બી. માટે એક અભિન્ન ઉકેલ માટે x ને ગોળાકાર કરો. અપૂર્ણાંક ભાગ માટે મોટા ભાગના ડબ્બામાં ઉમેરો. ડબ્બાઓની કુલ સંખ્યા છે. 2-બી. મોટાભાગની કે ડબ્બાઓમાં વસ્તુઓને પેક કરો; એક પેકિંગ મેળવો. ડબ્બાની સંખ્યા છે. 1-બી. ઉકેલ મેળવવા માટે જી કરતા નાની વસ્તુઓ ઉમેરો. ડબ્બાઓની સંખ્યા છેઃ એકંદરે, ડબ્બાઓની સંખ્યા અંદર છે અને રન-ટાઇમ અંદર છે. પસંદ કરવાથી આપણને મળે છે. અલ્ગોરિધમ 2 ચાલો એક વાસ્તવિક પરિમાણ અને પૂર્ણાંક પરિમાણ હોઈએ જે પછીથી નક્કી કરવામાં આવશે. 1-એ. ચાલો ઉદાહરણ તરીકે જી. 2 કરતા નાની બધી વસ્તુઓને દૂર કરીને બનાવવામાં આવે છે. જ્યારે કરવુંઃ 2-એ. પરિમાણ k સાથે વૈકલ્પિક ભૌમિતિક જૂથ બનાવો. ચાલો પરિણામી ઉદાહરણ બનીએ, અને બાકીનું ઉદાહરણ બનીએ. આપણી પાસે છે. 3-એ. અખંડિતતાની મર્યાદાઓ વિના, માટે રૂપરેખાંકન રેખીય કાર્યક્રમની રચના કરો. 4. x માટે સોલ્યુશનની ગણતરી કરો, જેમાં ટોલરન્સ h = 1 છે. પરિણામ એ છે કે ડબ્બા સાથે અપૂર્ણાંક ડબ્બા પેક કરવામાં આવે છે. રન-ટાઇમ છે. 3-બી. માટે એક અભિન્ન ઉકેલ માટે x ને ગોળાકાર કરો. અપૂર્ણાંક ભાગ માટે ડબ્બો ઉમેરશો નહીં. તેના બદલે, ફક્ત પેક કરેલી વસ્તુઓને દૂર કરો. 2-બી. મોટાભાગની ડબ્બાઓમાં વસ્તુઓને પેક કરો. 2. એકવાર, બાકીની વસ્તુઓને મોટાભાગના ડબ્બામાં લોભી રીતે પેક કરો. પગલું 2 માં લૂપના દરેક પુનરાવર્તન પર, x નો અપૂર્ણાંક ભાગ મહત્તમ m (K) પેટર્ન ધરાવે છે, તેથી. દરેક પુનરાવર્તનમાં એફ. ઓ. પી. ટી. k ના પરિબળ દ્વારા ઘટી જાય છે, તેથી પુનરાવર્તનોની સંખ્યા મહત્તમ હોય છે. તેથી, ઉપયોગમાં લેવાતા ડબ્બાઓની કુલ સંખ્યા છેઃ 1-બી. ઉકેલ મેળવવા માટે જી કરતા નાની વસ્તુઓ ઉમેરો. ડબ્બાઓની સંખ્યા છેઃ રન-ટાઇમ અંદર છે. હવે, જો આપણે k = 2 અને g = 1/FOPT (I) પસંદ કરીએ, તો આપણને મળે છેઃ, અને તેથીઃ, તેથી ડબ્બાઓની કુલ સંખ્યા અંદર છે. રન-ટાઇમ છે. સમાન અલ્ગોરિધમનો ઉપયોગ ચોકસાઈ સાથે રન-ટાઇમને ટ્રેડ-ઓફ કરવા માટે વિવિધ પરિમાણો સાથે થઈ શકે છે. કેટલાક પરિમાણો માટે, અને પસંદ કરો. પછી, પેકિંગને મોટાભાગના ડબ્બામાં જરૂર પડે છે, અને રન-ટાઇમ અંદર છે. અલ્ગોરિધમ 3 ત્રીજું અલ્ગોરિધમ ત્યારે ઉપયોગી થાય છે જ્યારે m કદની સંખ્યા ઓછી હોય (ઉચ્ચ-ગુણાકાર બિન પેકિંગ પણ જુઓ). 1-એ. સેટ કરો. ચાલો ઉદાહરણ તરીકે જી કરતા નાની બધી વસ્તુઓને દૂર કરીને બનાવવામાં આવે. જો એમ હોય તોઃ 3-એ. અખંડિતતાની મર્યાદાઓ વિના, માટે રૂપરેખાંકન રેખીય કાર્યક્રમની રચના કરો. 4. x માટે સોલ્યુશનની ગણતરી કરો, જેમાં ટોલરન્સ h = 1 છે. પરિણામ એ છે કે ડબ્બા સાથે અપૂર્ણાંક ડબ્બા પેક કરવામાં આવે છે. રન-ટાઇમ છે. 3-બી. માટે એક અભિન્ન ઉકેલ માટે x ને ગોળાકાર કરો. અપૂર્ણાંક ભાગ માટે ડબ્બો ઉમેરશો નહીં. તેના બદલે, ફક્ત પેક કરેલી વસ્તુઓને દૂર કરો. બાકીના ટુકડાઓ પર એલ્ગોરિધમ 2 નું પગલું 2 ચલાવો. 1-બી. ઉકેલ મેળવવા માટે જી કરતા નાની વસ્તુઓ ઉમેરો. ડબ્બાઓની સંખ્યા છેઃ તે મોટાભાગના ડબ્બામાં ઉપયોગ કરે છે, અને રન-ટાઇમ અંદર હોય છે. સુધારાઓ વધુ સારા અંદાજો પૂરા પાડવા માટે કેકે તકનીકોમાં પાછળથી સુધારો કરવામાં આવ્યો હતો. રોથવોસ એલ્ગોરિધમ 2 જેવી જ યોજનાનો ઉપયોગ કરે છે, પરંતુ પગલું 2 માં એક અલગ ગોળાકાર પ્રક્રિયા સાથે. તેમણે એક "ગ્લુઇંગ" પગલું રજૂ કર્યું, જેમાં નાની વસ્તુઓને એક મોટી વસ્તુ મેળવવા માટે એક સાથે જોડવામાં આવે છે. આ ગ્લુઇંગનો ઉપયોગ સૌથી નાની વસ્તુનું કદ લગભગ વધારવા માટે થઈ શકે છે. જ્યારે તમામ કદ ઓછામાં ઓછા હોય, ત્યારે આપણે અલ્ગોરિધમ 2 ની બાંયધરીમાં બદલી શકીએ છીએ, અને મેળવી શકીએ છીએઃ, જે ડબ્બા આપે છે. હોબર્ગ અને રોથવોસ એક સમાન યોજનાનો ઉપયોગ કરે છે જેમાં વસ્તુઓને પહેલા "કન્ટેનર" માં પેક કરવામાં આવે છે, અને પછી કન્ટેનરને ડબ્બામાં પેક કરવામાં આવે છે. તેમના અલ્ગોરિધમને મોટાભાગના ડબ્બાની જરૂર હોય છે. સંદર્ભો બિન પેકિંગ