बिन पैकिंग गतिशील प्रोग्रामिंग प्रश्न

Question

आपके पास आकार s1 के n1 आइटम, आकार s2 के n2 आइटम, और आकार s3 के n3 आइटम हैं। आप इन सभी वस्तुओं को क्षमता सी के प्रत्येक डिब्बे में पैक करना चाहते हैं, जैसे कि इस्तेमाल किए गए डिब्बे की कुल संख्या कम हो जाती है।

हम न्यूनतम संख्या में डिब्बे का उपयोग करके समाधान कैसे प्राप्त कर सकते हैं? लालची निश्चित रूप से काम नहीं कर रहा है।

Answer 1

यह एक बेवकूफ सवाल नहीं है, आईएमओ।

सामान्य रूप से बिन पैकिंग एनपी-पूर्ण होने के लिए जाना जाता है।

लेकिन आपका मामला, ऑब्जेक्ट भार की निश्चित संख्या के साथ बिन पैकिंग एक दिलचस्प संस्करण है।

निम्नलिखित पेपर का दावा बहुपद समय एल्गोरिदम है जो इष्टतम 1 के साथ आता है: http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310 जब आप 3 अलग-अलग आकारों की अनुमति देते हैं। (चेतावनी: मैं केवल सार द्वारा जा रहा हूँ)।

तो मुझे लगता है कि यह संस्करण एनपी-हार्ड भी है और लालची एल्गोरिदम संभवतः काम नहीं करेगा। गतिशील प्रोग्रामिंग के बारे में इतना निश्चित नहीं है (बिन पैकिंग दृढ़ता से एनपी-पूर्ण है)।

उम्मीद है कि मदद करता है।

Answer 2

आप अपनी समस्या को कम कर सकते हैं एक 1 दिन बिन-पैकिंग आप एक लालची यहां इस्तेमाल किया एल्गोरिथ्म का उपयोग करना चाहते: http://www.developerfusion.com/article/5540/bin-packing

Answer 3

तो आकार एकआयामी है, या अगर यह एक एकआयामी मूल्य को कम किया जा सकता है, तो आप हल कर सकते हैं यह एक बहु-बोरी knapsack समस्या (एमकेपी) के रूप में, जहां एक आइटम का वजन इसके लाभ के बराबर है। यदि आप उपलब्ध वस्तुओं की संख्या के लिए ऊपरी बाउंड पर #bin सेट करते हैं (एक नज़र में, यदि आपका उदाहरण बहुत अधिक नहीं है, तो यह मान #items हो सकता है), आप इस समस्या को शाखा के साथ बेहतर ढंग से हल कर सकते हैं या बाध्य या अन्य अनुकूलन एल्गोरिदम। यदि आप एक गैर-इष्टतम समाधान स्वीकार कर सकते हैं, तो कुछ व्यवहार्य लालची एल्गोरिदम हैं।

हालांकि, मुझे इतना यकीन नहीं है क्योंकि मैंने कभी भी इस समस्या का गहराई से अध्ययन नहीं किया है। फिर भी, "Knapsack Problems" नामक एक पुस्तक है जो बिन पैकिंग समस्याओं सहित फॉर्मूलेशन और एल्गोरिदम प्रस्तुत करती है। इसे इंटरनेट में पीडीएफ के रूप में नहीं ढूंढना मुश्किल है।

इस सहायता की आशा करें। सौभाग्य।

Answer 4

उत्कृष्ट पैकिंग संभालने डिब्बे की न्यूनतम संख्या B = ceiling(sum(n(i)*s(i) for i in 1..3)/C)

उपयोग क्या हुआ अगर आइटम बी डिब्बे में फिट देखने के लिए first_fit कहा जाता है, लेकिन वास्तव में worst_fit है, अदला-बदली के साथ, here से होगा। यदि नहीं, तो बी बढ़ाएं और फिट होने तक दोहराएं।

Answer 5

यह कुशल नहीं होगा, लेकिन आप इस को polinomial समय में एक सीधा गतिशील प्रोग्रामिंग एल्गोरिदम के साथ हल कर सकते हैं। बहुपद की डिग्री आपके पास विभिन्न आकारों की संख्या पर निर्भर करेगी।

मैंने एक कार्यान्वयन शामिल किया है कि 3 अलग-अलग आकारों के लिए O(n1 * n2 * n3 * (C/s2) * (C/s3) * ((n1*s1 + n2*s2 + n3*s3)/C)) एक सुंदर क्रैपी स्थिरांक के साथ होगा। (यह आंकड़ा इस तथ्य की सौजन्य है कि हम उपलब्धता के विशिष्ट पैटर्न की संख्या O(n1 * n2 * n3) है और प्रत्येक के लिए हम O((C/s2) * (C/s3)) उत्पन्न करने के लिए अगले डिब्बे को संभव बनाने के लिए उत्पन्न करते हैं, जिनमें से प्रत्येक के लिए हमें डिब्बे के सेट के साथ काम करना होता है जिसका आकार O((n1*s1 + n2*s2 + n3*s3)/C)) है। कई नियमित अनुकूलन इस कार्यक्रम को बड़े पैमाने पर बढ़ा सकते हैं।)

#! /usr/bin/python 
import heapq 

def min_bins(bin_size, sizes, counts): 
    available = zip(sizes, counts) 
    available.sort(reverse=True) 
    seen = set([]) 
    upcoming = [(0, available, [])] 
    while 0 < len(upcoming): 
     (n, available, bins) = heapq.heappop(upcoming) 
     for (bin, left) in bin_packing_and_left(bin_size, available): 
      new_bins = bins + [bin] 
      if 0 == len(left): 
       return new_bins 
      elif left not in seen: 
       heapq.heappush(upcoming, (n+1, left, new_bins)) 
       seen.add(left) 

def bin_packing_and_left(bin_size, available, top=True): 
    if 0 == len(available): 
     yield ((),()) 
    else: 
     (size, count) = available[0] 
     available = available[1:] 
     for (bin, left, used) in bin_packing_and_left_size(bin_size, available): 
      can_use = (bin_size - used)/size 
      if count <= can_use: 
       yield(((size, count),) + bin, left) 
      elif 0 < can_use: 
       yield(((size, can_use),) + bin, 
         ((size, count - can_use),) + left) 
      else: 
       yield(bin, ((size, count),) + left) 

def bin_packing_and_left_size(bin_size, available): 
    if 0 == len(available): 
     yield ((),(), 0) 
    else: 
     (size, count) = available[0] 
     available = available[1:] 
     for (bin, left, used) in bin_packing_and_left_size(bin_size, available): 
      for i in range(1 + min(count, (bin_size - used)/size)): 
       if count == i: 
        yield(((size, count),) + bin, left, used + size * count) 
       elif 0 < i: 
        yield(((size, i),) + bin, 
          ((size, count - i),) + left, 
          used + size * i) 
       else: 
        yield(bin, ((size, count),) + left, used) 

answer = min_bins(23, (2, 3, 5), (20, 30, 40)) 
print len(answer) 
print answer 

Answer 6

यहां इस के लिए डीपी एल्गोरिदम का एक स्केच है।

रिकर्सिव रिलेशनशिप: हम B(i, j, k) पर रिकर्स करते हैं, आकार सी के आइटमों की न्यूनतम संख्या, आकार एस 2 के जे आइटम और आकार एस 3 के आइटमों को पैक करने के लिए आवश्यक न्यूनतम सी के डिब्बे की आवश्यकता होती है। संबंध है:

B(i, j, k) = min {B (x,y,z) , B(i-x, j-y, k-z)} 
where 0<=x<=i; 
0<=y<=j; 
0<=z<=k 

जहां x, y या z कम से कम एक से अधिक 0 और x में से एक, y या z होना चाहिए कम से कम i, j या k होनी चाहिए।

रनिंग समय: बी आकार ओ (एन 3) है और बी के प्रत्येक तत्व की गणना करने के लिए ओ (एन 6) के कुल समय के लिए समय ओ (एन 3) की आवश्यकता होती है।

Answer 7

यह O(n1*n2*n3) में किया जा सकता ...

कहना चलें, f(i,j,k) न्यूनतम नहीं है। डिब्बे कि आकार s1, s2 की i, j और k आइटम, s3 क्रमशः फिट करने के लिए आवश्यक हैं ..

नोट की: सी बिन

f(i,j,k) की क्षमता के बारे में जानकारी के 2 प्रकार का आयोजन करेगा है:

ए) (The min no. of bins that are currently required) - 1। कहें संपत्ति B1 है।

ख) पिछले बिन के वर्तमान आकार जो आगे दाखिल के लिए उपलब्ध है .. कहो संपत्ति B2 .. जहां 0 < B2 <= C

इसलिए, पुनरावृत्ति होगा:

f(i,j,k)([B1],[B2]) = 
    min 
{ 
    f(i-1, j, k)([B1] + [B2 + S1]/(C+1) , [B2 + S1] <=C ? [B2 + S1] : [B2 + S1 - C]) , 
    f(i, j-1, k)([B1] + [B2 + S2]/(C+1) , [B2 + S2] <=C ? [B2 + S2] : [B2 + S2 - C]) , 
    f(i, j, k-1)([B1] + [B2 + S3]/(C+1) , [B2 + S3] <=C ? [B2 + S3] : [B2 + S3 - C]) 
} 

न्यूनतम नहीं। डिब्बे की आवश्यकता: 1 + f(n1, n2, n3)[B1]

Answer 8

यदि हम एक बिन के इष्टतम समाधान पा सकते हैं, तो इसका मतलब है कि मैं एक बिन में अधिकतम तत्वों को फिट कर सकता हूं, इससे इसका जवाब होगा।

आइए आकार एस 1 के तत्वों को मानें, आकार एस 2 के बी तत्व, आकार एस 3 के सी तत्व तत्वों की अधिकतम संख्या हैं जिन्हें मैं एक बिन में फिट कर सकता हूं। तो अधिकतम बिन जो मैं एक बिन में फिट कर सकता हूं वह है = ए * एस 1 + बी * एस 2 + सी * एस 3। तो जवाब होगा (एन 1 * एस 1 + एन 2 * एस 2 + एन 3 * एस 3)/के + (एन 1 * एस 1 + एन 2 * एस 2 + एन 3 * एस 3)% के डिब्बे की संख्या।

ढूँढना कश्मीर मानक बस्ता परेशानी की तुलना में आसान मुझे लगता है कि सभी इष्टतम मूल्यों तक मैं मौजूद है 1 < है = मैं < = C.Then की i + 1 रिकर्सिवली

M(i+1) = max(M(i),M(i-S1)+S1,M(i-S2)+S2,M(i-S3)+S3).