अधिकतम वजन के साथ एक लिफ्ट को देखते हुए और एन x_i वजन के साथ लोगों को, जरूरत की सवारी की न्यूनतम संख्या का पता लगाने के

Question

input: 
max_weight = 550 
n = 4 
x_i = [120, 175, 250, 150] 

output: 
2 
// [[250, 175, 120], [150]] 

मेरे प्रारंभिक धारणा है कि यह बहुत ही एक गतिशील प्रोग्रामिंग सिक्का परिवर्तन/नेप्सेक समस्या के समान दिखता है, लेकिन यह सिक्के नहीं है परिवर्तन (जो सटीक राशि बनाने के लिए वजन की सबसे कम संख्या के लिए पूछेगा), और यह knapsack नहीं है (वजन के मूल्य नहीं हैं और ऐसा लगता है कि मैं 1 से अधिक knapsack हो सकता है)।

क्या इस समस्या के लिए कोई आम नाम/समाधान है?

Answer 1

यह वास्तव में है एक (1D) Bin Packing problem:

बिन पैकिंग समस्या में, अलग-अलग मात्रा की वस्तुओं डिब्बे के एक परिमित संख्या या कंटेनर मात्रा से प्रत्येक वी एक तरह से में पैक किया जाना चाहिए का उपयोग किए गए डिब्बे की संख्या को कम करता है। कम्प्यूटेशनल जटिलता सिद्धांत में, यह एक संयोजक एनपी-हार्ड समस्या है।

यहां लोग सवारी पर डिब्बे में वस्तुओं पर नक्शा लगाते हैं। बिन पैकिंग समस्या की तरह हम "उपयोग" की सवारी की संख्या को कम करना चाहते हैं और प्रत्येक व्यक्ति एक निश्चित "मात्रा" (उस व्यक्ति का वजन) पर कब्जा करता है।

बिन पैकिंग समस्या है - लेख में कहा गया - एनपी-हार्ड। हम गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं (लेकिन यह अभी भी है - सबसे खराब मामला - घातीय समय)।

पेपर A New Algorithm for Optimal Bin Packingरिचर्ड ई। कॉर्फ इस समस्या को हल करने के लिए एक एल्गोरिदम पर चर्चा करता है। यह पहले एक ह्युरिस्टिक दृष्टिकोण का उपयोग करके और निचले बाउंड की गणना करके काम करता है, और उसके बाद शाखा का उपयोग करता है और निचले स्तर तक पहुंचने तक एक बेहतर समाधान प्राप्त करने के लिए बाध्य होता है, या अब कोई समाधान नहीं मिल सकता है।

Answer 2

अगर मैं गलत हूं (सबसे कुशल नहीं) तो कृपया मुझे सही करें, लेकिन मुझे लगता है कि आप सभी वजन max heap में डाल सकते हैं, और फिर सेट चुनने के लिए greedy algorithm का उपयोग करें।

Answer 3

आप सही रास्ते पर हैं। समस्या को एक संशोधित सिक्का-परिवर्तन एल्गोरिदम द्वारा हल किया जाता है: एक सटीक समाधान की मांग करने के बजाय, आपको वह लक्ष्य मिलता है जो लक्ष्य राशि से अधिक किए बिना उच्चतम कुल प्राप्त करता है। बेशक, अगर आपको कोई समाधान मिलता है जिसका कमी किसी भी शेष सेट तत्व से कम है, तो आप उस समाधान को रोकें और रिपोर्ट करें।

जब आपको कोई समाधान मिल जाए, तो "उपयोग" वजन को हटा दें और तब तक इसे तब तक हटा दें जब तक आप उन्हें आवंटित नहीं करते। पुनरावृत्तियों की संख्या आपको आवश्यक लिफ्टों की मात्रा है।

यदि आप तत्वों को अवरोही क्रम में क्रमबद्ध करते हैं, तो यह आपको बैकट्रैकिंग के साथ शुरूआत में "लालची" देता है। मुझे संदेह है कि यह कई मामलों के लिए इष्टतम के करीब है, खासकर यदि आप परिणामों को याद करते हैं ताकि आप अगले पुनरावृत्ति पर गलतियों को दोहराएं।

आप इस तरह के 100 की एक सीमा के रूप में कुछ रोग मामलों, और चरम वजन की तरह

[93, 91, ..., 5, 4, 4] 

"लालची" एल्गोरिथ्म पहले 93 + 5 के लिए चला जाता है की कोशिश कर सकते, लेकिन बाद में 91 + 4 + 4 के लिए सुलझेगी (करीब समाधान)। यह वह जगह है जहां यादगार काम में आता है।

क्या यह आपको समाधान के लिए ले जाता है?