बेसिक एल्गोरिथ्म सबूत

Question

मैं उदाहरण के लिए संख्या का एक अनुक्रम है,: 170, 205, 225, 190, 260, 130, 225, 160 और मैं उन्हें तत्वों ताकि अधिक से अधिक अंतर सेट के तत्वों के बीच कम से कम है की निश्चित संख्या के साथ सेट में विभाजित किया है।

मुझे गारंटी है कि अगर मुझे तत्वों को K तत्वों के सेट में विभाजित करने की आवश्यकता है, तो तत्वों की वैश्विक संख्या Z * K के बराबर होती है।

(1) : 130 160 170 190(अधिकतम अंतर 60 के बराबर होती है)

(2) : 205 225 225 260(अधिकतम अंतर के बराबर होती है 55)

:

K = 4 साथ उदाहरण के लिए, इष्टतम बंटवारे इस तरह से किया जा सकता है perfomed

तो, इस मामले के लिए वैश्विक अधिकतम अंतर 60 के बराबर है।

---

अब, सवाल: मेरी धारणा है कि मैं यह कर सकते हैं बस प्रकार प्रारंभिक डेटा और यह और भी प्रारंभ से लेकर भागों में विभाजित है? यदि यह सही है, तो मैं इसे कैसे साबित कर सकता हूं? और यदि यह नहीं है, तो इस समस्या को हल करने के लिए मुझे किस दृष्टिकोण का उपयोग करना चाहिए?

Answer 1

मानते हैं कि आपकी संख्याओं की संख्या हमेशा के द्वारा विभाजित की जा सकती है (इसलिए 4 के सेट में 13 नंबर नहीं), यह सही है।

सॉर्टिंग के माध्यम से, आपको संभवतः एक-दूसरे के करीब जितना संभव हो उतना समान संख्या मिलती है। सवाल यह है कि, यदि संख्याओं को किसी भी सेट में सबसे खराब मूल्य को निकट मूल्यों के साथ लाने के लिए स्थानांतरित किया जाता है, तो क्या इससे अधिकतम अंतर छोटा हो जाता है?

उत्तर नहीं है। सॉर्ट किए जाने पर, संख्या के बाईं ओर स्थित एकमात्र मान बराबर या कम होते हैं, जो बाईं ओर जाने वाली संख्या कम मानों से घिरा होगा। अधिकतम संख्या के कारण होने वाली दो संख्याओं में से कम से कम एक को और भी बदतर साथी मिलेगा, जिसका अर्थ है कि आपकी अधिकतम दूरी अधिक हो जाएगी। यह वही काम करता है जो दाएं कोने के साथ सही होता है।

Sorted: 
[lowest, low, low, x] distance1 = x-lowest 
[y, high, high, highest] distance2 = highest-y 

Swapped: 
[lowest, low, low, y] distance3 = y-lowest 
[x, high, high, highest] distance4 = highest-x 

के बाद से एक्स < y (मान लेते हैं वे गमागमन व्यर्थ होगा के बाद से बराबर नहीं कर रहे हैं भी नहीं), distance3> distance1 और distance4> distance2, जिसका अर्थ है चीजों को और बिगड़ गया।

यदि आप वहां उच्च मूल्य डालते हैं तो यह वैसे ही काम करता है।

कोई फर्क नहीं पड़ता कि संख्या कितनी दूर है, उस स्थान पर एक और नंबर डालने से उन्हें और अधिक दूर कर दिया जाएगा।

एक अन्य विकल्प पूरे सबसेट एक अंतरिक्ष छोड़ दिया स्थानांतरित करने के लिए है:

[lowest, low, low, y] 
[high, high, highest, x] 

लेकिन यह वास्तव में अदला-बदली के रूप में एक ही परिणाम है।

तो यह 2 सेट के साथ काम करता है।

तीन सेट के साथ

:

[lowest, low, low, x] 
[lowM, lowM, highM, highM] 
[highM, y, high, highest] 

गमागमन x और y पहले के समान है। यहां तक ​​कि यदि एक्स बहुत समान है या यहां तक ​​कि नीचे बाएं उच्च के बराबर है (यदि मध्य निम्न और उच्च वास्तव में बराबर हैं), y अभी भी x से अधिक है, जिससे अंतर सबसे अधिक हो गया है, और x उच्चतम से दूर है।

संख्या आगे का एक समूह आगे बढ़ते:

[lowest, low, lowM, lowM] 
[highM, highM, highM, y] 
[x, highM, high, highest]; 

शायद सबसे बड़ा अंतर highM और उच्चतम के बीच था, और उस दूरी अब निकाल दिया जाता है। लेकिन चूंकि आप इसे यहां तक ​​कि कम मूल्य डालकर केवल उच्चतम स्थान से दूर ले जा सकते हैं, इसलिए आप हमेशा इसे और खराब बनाते हैं। उच्चतम दूरी उच्चतम उच्चतम अब उच्चतम x है, और x < हाईएम है।

यह अभी भी दूसरे तरीके से काम करता है। अगर कोई अगला सेट होता, तो उच्चतम के साथ उच्चतम संख्या के साथ हाईएम को बदल दिया जा सकता था, लेकिन यह उच्चतम संख्याओं के साथ उच्चतम स्थान भी लगाएगा जिससे इससे भी अधिक अंतर आएगा।

तो हाँ, डेटा को सॉर्ट करना और फिर इसे बराबर भागों में विभाजित करना हमेशा आपको न्यूनतम अधिकतम अंतर देता है, क्योंकि सॉर्ट किए गए सेट को बदलना हमेशा खराब परिणाम देता है।

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

Answer 2

यदि प्रारंभिक अनुक्रम क्रमबद्ध किया गया है तो आसन्न संख्याओं में सबसे छोटा अंतर होना चाहिए।

इसके अलावा शुरुआत में और अनुक्रम के अंत में तत्वों का सबसे बड़ा अंतर होना चाहिए।

परिणामस्वरूप अनुक्रम का कोई भी "कट" जिसमें अंतिम तत्व और पहला तत्व शामिल है, समाधान का हिस्सा नहीं हो सकता क्योंकि इसमें न्यूनतम अंतर नहीं है।

तो विभाजन शुरू होने से शुरू होने वाले हिस्सों में संख्याओं के अनुक्रम को विभाजित करके किया जाना चाहिए।

ऐसा लगता है कि आपका दृष्टिकोण सही है, लेकिन मैं इसके लिए अधिक औपचारिक प्रमाण नहीं सोच सकता।

Answer 3

स्वाभाविक रूप से आपको उन्हें क्रमबद्ध करके संख्याओं के जोड़ों के बीच सबसे छोटा अंतर मिलेगा। आप आसानी से क्रमबद्ध संख्याओं को विभाजित करके छोटे अंतरों के साथ सेट प्राप्त कर सकते हैं।

कुछ मामलों में आप अधिकतम सेट को अधिकतम किए बिना सेट के बीच संख्याओं को स्विच कर सकते हैं, इसलिए संख्याओं को सेट में विभाजित करने के एक से अधिक तरीके हो सकते हैं जो समान अधिकतम अंतर देता है। हालांकि, आप अधिकतम सेट को अधिकतम किए बिना अधिकतम सेट को कम करने के लिए सेट के बीच संख्याओं को स्विच नहीं कर सकते हैं।

आप उदाहरण के लिए सेट 1,3,4,5 और 6,7,8,10 है, तो आप 5 और 6 या तो समूह में अधिकतम अंतर में वृद्धि के बिना बदल सकते हैं।

यदि आप अंतरों के सबसे छोटे औसत चाहते हैं, तो आप एक सेट में अधिकतम अंतर को दूसरे सेट में अंतर कम करने के लिए त्याग सकते हैं।