बस मस्ती के लिए मैंने सटीक गतिशील प्रोग्रामिंग समाधान की कोशिश की। पाइथन में लिखा गया है कि मेरे सर्वोच्च विश्वास के कारण आपको इसे अनुकूलित नहीं करना चाहिए ;-)
यह या तो एक शुरुआत प्रदान कर सकता है, या फिर अनुमान लगा सकता है कि आप अनुमान लगाने से पहले कितना करीब प्राप्त कर सकते हैं।
कोड http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem पर आधारित है, इसलिए कम-से-जानकारीपूर्ण चर नाम m, W, w, v।
#!/usr/bin/python
import sys
solcount = 0
class Solution(object):
def __init__(self, items):
object.__init__(self)
#self.items = items
self.value = sum(items)
global solcount
solcount += 1
def __str__(self):
#return str(self.items) + ' = ' + str(self.value)
return ' = ' + str(self.value)
m = {}
def compute(v, w):
coord = (len(v),w)
if coord in m:
return m[coord]
if len(v) == 0 or w == 0:
m[coord] = Solution([])
return m[coord]
newvalue = v[0]
newarray = v[1:]
notused = compute(newarray, w)
if newvalue > w:
m[coord] = notused
return notused
# used = Solution(compute(newarray, w - newvalue).items + [newvalue])
used = Solution([compute(newarray, w - newvalue).value] + [newvalue])
best = notused if notused.value >= used.value else used
m[coord] = best
return best
def main():
v = [int(l) for l in open('filesizes.txt')]
W = int(sys.argv[1])
print len(v), "items, limit is", W
print compute(v, W)
print solcount, "solutions computed"
if __name__ == '__main__':
main()
सरलता के लिए मैं सिर्फ फ़ाइल आकार पर विचार कर रहा हूँ: एक बार आप आकार है कि आप उपयोग करना चाहते हैं की सूची है, तो आप एक सूची के माध्यम से खोज से उन आकारों के साथ कुछ फ़ाइल नाम मिल सकता है, इसलिए वहाँ कोई मतलब नहीं tangling है कोर में फ़ाइल नाम, कार्यक्रम के धीमे भाग। मैं ब्लॉक आकार के गुणकों में सबकुछ भी व्यक्त कर रहा हूं।
जैसा कि आप देख सकते हैं, मैंने उस कोड को टिप्पणी की है जो वास्तविक समाधान (समाधान के मूल्य के विपरीत) देता है। यह स्मृति को सहेजना था - उपयोग की गई फ़ाइलों की सूची को स्टोर करने का उचित तरीका प्रत्येक समाधान में एक सूची नहीं है, यह प्रत्येक समाधान को हल किए गए समाधान पर वापस इंगित करना है। फिर आप प्रत्येक चरण में मानों के बीच अंतर को आउटपुट करते हुए श्रृंखला के माध्यम से वापस जाकर अंत में फाइलों की सूची की गणना कर सकते हैं।
2000-6000 की सीमा में 100 यादृच्छिक रूप से जेनरेट की गई फ़ाइल आकारों की एक सूची के साथ (मैं 2k ब्लॉक मान रहा हूं, इसलिए आकार 4-12 एमबी की फाइलें हैं), यह मेरे लैपटॉप पर 100 सेकंड में डब्ल्यू = 40 के लिए हल करता है । ऐसा करने में यह एक संभावित 4 एम समाधान के 2.6 एम की गणना करता है।
जटिलता ओ (डब्ल्यू * एन) है, जहां एन फाइलों की संख्या है। यह इस तथ्य का खंडन नहीं करता है कि समस्या एनपी-पूर्ण है। तो मैं कम से कम एक समाधान के पास आ रहा हूं, और यह सिर्फ अनियंत्रित पायथन में है।
स्पष्ट रूप से कुछ अनुकूलन की आवश्यकता है, क्योंकि वास्तव में इसे डब्ल्यू = 4 एम (8 जीबी डीवीडी) के लिए हल करने की आवश्यकता है और हालांकि आपके पास कई फाइलें हैं (कुछ हज़ार कहें)। यह मानते हुए कि कार्यक्रम को 15 मिनट (डीवीडी लिखने के लिए आवश्यक समय के बराबर) लेने की अनुमति है, इसका मतलब है कि प्रदर्शन वर्तमान में लगभग 10^3 के कारक से छोटा है। इसलिए हमें एक समस्या है जो एक पीसी पर जल्दी और सटीक हल करने में काफी मुश्किल है, लेकिन प्रौद्योगिकी की सीमाओं से परे नहीं है।
स्मृति उपयोग मुख्य चिंता है, क्योंकि एक बार जब हम स्वैप मारना शुरू कर देते हैं तो हम धीमे हो जाएंगे, और यदि हम वर्चुअल एड्रेस स्पेस से बाहर निकलते हैं तो हम वास्तविक परेशानी में हैं क्योंकि हमें डिस्क पर समाधानों का अपना संग्रहण लागू करना है । मेरा परीक्षण 600 एमबी पर चोटी चलाता है। यदि आपने 32-बिट मशीन पर सी में कोड लिखा है, तो प्रत्येक "समाधान" में 8 बाइट्स का निश्चित आकार होता है। इसलिए आप लूप में कोई स्मृति आवंटन किए बिना उनमें से एक विशाल 2-डी सरणी उत्पन्न कर सकते हैं, लेकिन 2 जीबी रैम में आप केवल W = 4M और n = 67 को संभाल सकते हैं। ओह - डीवीडी बाहर हैं। यह लगभग 2-के अवरोधक सीडी के लिए लगभग हल हो सकता है, हालांकि: डब्ल्यू = 350k एन = 766 देता है।
संपादित करें: एमएके के सुझाव को क्रमशः नीचे-नीचे की तुलना में नीचे की ओर गणना करने के लिए, स्मृति की आवश्यकता को बड़े पैमाने पर कम करना चाहिए। सबसे पहले 0 < = डब्ल्यू < = डब्ल्यू के लिए एम (1, डब्ल्यू) की गणना करें। इस सरणी से, आप सभी= डब्ल्यू < = डब्ल्यू के लिए एम (2, डब्ल्यू) की गणना कर सकते हैं। फिर आप सभी एम को फेंक सकते हैं (1, डब्ल्यू) मूल्य: आपको एम (3, डब्ल्यू) आदि की गणना करने की आवश्यकता नहीं होगी
वैसे, मुझे संदेह है कि वास्तव में जिस समस्या को आप हल करना चाहते हैं वह bin packing problem हो सकता है, केवल प्रश्न के बजाय एक डीवीडी भरने के लिए निकटतम संभव कैसे प्राप्त करें। ऐसा लगता है कि यदि आपके पास फाइलों का एक गुच्छा है, तो आप उन्हें डीवीडी पर लिखना चाहते हैं, जितना संभव हो उतने डीवीडी का उपयोग कर। ऐसी स्थितियां हैं जहां बिन पैकिंग समस्या को हल करना बहुत आसान है, लेकिन इस समस्या को हल करना मुश्किल है। उदाहरण के लिए, मान लीजिए कि आपके पास 8 जीबी डिस्क हैं, और 15 जीबी छोटी फाइलें हैं। यह 8 जीबी के निकटतम संभावित मैच को खोजने के लिए कुछ खोज करने जा रहा है, लेकिन बिन-पैकिंग समस्या को केवल प्रत्येक डिस्क पर लगभग आधे फाइलों को डालकर हल किया जाएगा - इससे कोई फ़र्क नहीं पड़ता कि आप उन्हें कैसे विभाजित करते हैं क्योंकि आप हैं जो भी आप करते हैं 1 जीबी स्पेस बर्बाद करने जा रहे हैं।
जो कुछ भी कहा गया है, वहां बहुत तेज़ हेरिस्टिक हैं जो समय के सभ्य परिणाम देते हैं। सरलतम फ़ाइलों की सूची (शायद आकार के घटते क्रम में) के माध्यम से जाना है, और यदि यह फिट बैठता है तो प्रत्येक फ़ाइल को शामिल करें, अन्यथा इसे बाहर करें। यदि आप "पर्याप्त" की पसंद के लिए तेजी से अनुमानित समाधान "पर्याप्त" नहीं हैं, तो आपको केवल कुछ भी धीमा करने की आवश्यकता है।
यह मुझे http://xkcd.com/287/ – ruslik
की याद दिलाता है मुझे लगता है कि सही समस्या परिभाषा होगी "इन फ़ाइलों को न्यूनतम संख्या में डिब्बे कैसे विभाजित करें, ताकि प्रत्येक बिन की फ़ाइलें अधिक न हों आकार सीमा। ", और यह नासैकैक की एक और मुश्किल समस्या है। – ruslik