संख्याओं की दो सूचियों का एक अच्छा मिलान ढूंढना

Question

मुझे SET2 के साथ आमतौर पर अधिक आइटम होने के साथ संख्याओं के दो सेट मिलते हैं। यह गारंटी है कि की गणना SET2SET1 की गणना से बराबर या अधिक है। एकजुट रूप से, चूंकि ऑर्डर महत्वपूर्ण है इनपुट इनपुट की तुलना में सूचियां हैं।

मेरा लक्ष्य (योग) SET2 से यह रूप में SET1 संभव के रूप में के समान बनाने के लिए गठबंधन करने के लिए/संख्या को पुन: व्यवस्थित है। मैं समानता को प्रत्येक स्थिति में विचलन के योग के रूप में परिभाषित करता हूं। जिस तरह से मैं समानता की गणना करता हूं, उसके लिए this post देखें। योग जितना छोटा होगा उतना ही बेहतर होगा।

मेरा पहला दृष्टिकोण सभी संयोजनों को आजमाने और सर्वोत्तम चुनने का था। यह केवल बहुत छोटे सेट के लिए काम करता है (एसएसपी दूसरा)। this post और रॉलिंग से उत्तर देखें। क्या अच्छा संयोजन पाने के लिए कोई शानदार तरीका है? मुझे निश्चित रूप से सबसे अच्छा की जरूरत नहीं है। परिणामस्वरूप एक अच्छा ठीक होगा। स्पष्ट रूप से खाली सबसेट वाले सेट बकवास हैं। बेहद असंतुलित सेट मेरे लिए बहुत ही आशाजनक प्रतीत नहीं होते हैं। एसईटी 1 में लगभग 8 है लेकिन इसमें 18 प्रविष्टियां हो सकती हैं। एसईटी 2 अक्सर 10 से अधिक (35 तक) की गिनती है। दो सेटों में संख्याओं का योग बराबर है (गोल करने वाली त्रुटियों को छोड़कर)।

SET1 = { 272370, 194560, 233430 }; SET2 = { 53407.13, 100000, 365634.03, 181319.07 } 

     272370   |  194560   |  233430 
--------------------------------------------------------------------- 
    365634.03   | 100000 + 53407.13 |  181319.07  (best match) 
    365634.03   |  181319.07  | 100000 + 53407.13 (good) 
    365634.03   |  100000   |181319.07 + 53407.13 (ok) 
     53407.13   |365634.03 + 100000 |  181319.07  (bad) 
     53407.13   |365634.03 + 181319.07 |  100000  (bad) 
.     |365634.03 + 181319.07 | 53407.13 + 100000 (invalid) 
53407.13 + 100000 |365634.03 + 181319.07 |      (invalid) 

कृपया मुझे बताएं कि मैं एक premiss वर्णन करने के लिए भूल गया या मेरे विवरण स्पष्ट नहीं या यहां तक ​​कि दोषपूर्ण है करते हैं:

यहाँ (सभी संभव वाले नहीं) अच्छे और बुरे परिणामों के साथ एक उदाहरण है। मैं एक और उदाहरण प्रदान करने में भी खुश हूं।

अग्रिम धन्यवाद!

Answer 1

अनुमानी है, जो काफी अच्छा काम करना चाहिए: उच्चतम से SET2 के माध्यम से पुनरावृति सबसे कम करने के लिए,, SET1 से वास्तविक उच्चतम तत्व प्राप्त तत्व द्वारा यह कमी SET2 से मिला है और इस तत्व जोड़ें:

1. list<int> set1, set2; 
2. sort(set2) // decreasing, set2[0] would be the greatest value in set2 
3. struct set1item = {set1index, value, list<int> chosen} 
4. prepare list<set1item> set1items from set1 //(index = index in set1 list, value = set1[index] and chosen = null) 
5. put set1items to some priorityqueue pq // ordered by value 
6. for each set2item in set2{ 
7.  item = pq.first() 
8.  item.chosen.add(set2item); 
9.  item.value -= set2item; 
10. pq.updateFirst(item) 
11.} 

ऐसा लगता है कि काम करेगा सेट 1 परिणामों से set2 से तत्व तक।

आपको यह जांचना याद रखना चाहिए कि सेट 1 के सभी तत्वों का कोई खाली परिणाम नहीं है या नहीं।

उदाहरण 1: Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}।

iter1: fromSet2 = 7, Set1 = {20:{}, 9:{}, 7:{}, 3:{}}, fromSet1=20। 7 से 20 की कमी और इसके परिणामस्वरूप 7 जोड़ना। अपडेट किया गया: Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}।

iter2: fromSet2 = 6, Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}, fromSet1=13। 6 से 13 घटाकर इसके परिणाम में 6 जोड़ना। अपडेट किया गया: Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}।

iter3: fromSet2 = 6, Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}, fromSet1=9। 9 से 9 तक घट रहा है और इसके परिणामस्वरूप 6 जोड़ रहा है। अपडेट किया गया: Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}।

iter4: fromSet2 = 4, Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}, fromSet1=7। 4 से 7 की कमी और इसके परिणाम में 4 जोड़ना। अपडेट किया गया: Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}।

iter5: fromSet2 = 2, Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}, fromSet1=7। 7 से 2 घटाना और इसके परिणाम में 2 जोड़ना। अपडेट किया गया: Set1 = {3:{7, 6, 4}, 3:{6}, 5:{2}, 3:{}}।

...