नोट: यह एक पूर्ण समाधान नहीं है, लेकिन मैं कुछ विचार साझा करना चाहता था। कृपया एक बेहतर समाधान आज़माएं और ढूंढें।
तो, हमारे पास n आवेदक हैं और m कौशल S = {s(1),s(2),...,s(m)} का एक सेट है।
प्रत्येक आवेदक, हमारे उद्देश्यों के लिए, S का एक सबसेट A है जो उसके कौशल को दर्शाता है।
t आवेदकों की संख्या चुनने की संख्या है (उदाहरण के लिए 3, या 6)।
के रूप में ओ पी ने कहा, हम लंबाई m के एक स्ट्रिंग है, जहां स्थिति i पर चरित्र 1 है अगर s(i)A के अंतर्गत आता है, और 0 यदि ऐसा नहीं होता है के रूप में प्रत्येक आवेदक के कौशल का प्रतिनिधित्व कर सकते हैं।
उदाहरण:
S = {Programming, Accounting}
Programming Accounting
Applicant1 0 1
Applicant2 1 1
आवेदकों
हम आवेदकों पर निम्न क्रम परिभाषित कर सकते हैं की संख्या कम: दो आवेदकों A1 और A2 को देखते हुए, हम कहते हैं कि a1 <= a2 केवल और केवल तभी करता है, तो निम्नलिखित कथन सत्य है: if a1 has a skill, then a2 also has it। उपर्युक्त उदाहरण में, हमारे पास Applicant1 <= Applicant2 है।
अब हम इस आदेश का उपयोग करके हमारे आवेदकों के सेट को फ़िल्टर कर सकते हैं: यदि कोई आवेदक ए 1 हमारे आदेश में एक अन्य आवेदक ए 2 "नीचे" है, तो ए 1 को चुनौती दे सकता है, क्योंकि ए 2 चुनने से कम से कम एक ही परिणाम मिलेगा। यह O(n^2) चरणों में किया जा सकता है।
गैर इष्टतम, लालची एल्गोरिथ्म
एक बार जब हम समाप्त कर दिया है, मैं इस तरह से आगे बढ़ना होगा:
r = string of lenght m filled with zeros
choose an applicant a
r = skills(a)
best_applicant = null
APPLICANT_LIST = new LIST
APPLICANT_LIST.add(a)
for(counter=0; counter < (t-1); counter ++)
{
foreach applicant b not in APPLICANT_LIST
{
if (count(skills(b) OR r) > count(r))
then
r = (skills(b) OR r)
best_applicant = b
}
APPLICANT_LIST.add(b)
}
अनिवार्य रूप से, मैं एक आवेदक a चुनें और उसकी/उसके कौशल r सेट के साथ शुरू होता है, और उसके बाद आवेदक b खोजें जो इसे अधिकतम करने के लिए मेरे मौजूदा सेट r पर सबसे अधिक कौशल जोड़ देगा। मैं अपनी सूची में b जोड़ूंगा, और प्रक्रिया को तब तक दोहरा दूंगा जब तक कि मेरे पास t आवेदकों का सेट न हो। यह सब O(n^2) चरणों में किया जाता है (चूंकि t स्थिर है, मैं इसे अनदेखा कर रहा हूं)। यह छद्म कोड प्रोग्रामिंग उद्देश्य से गलत हो सकता है (भाषा के आधार पर, आप निकास की स्थिति, शून्य पॉइंटर्स इत्यादि की जांच करना चाहेंगे), लेकिन मुझे यकीन है कि आपको यह विचार मिल जाएगा।
t = 3
a1 000000001111
a2 000011110000
a3 111100000000
a4 110111001101
एक अगर a4 साथ शुरू करने के लिए थे, वह इष्टतम समाधान {a1,a2,a3} के लिए कभी नहीं मिलेगा:
मैं, के रूप में इस उदाहरण के द्वारा दिखाया डर इस विधि हमेशा इष्टतम समाधान उपज नहीं है हूँ। यह वह कीमत है जिसे हम प्रत्येक समाधान पर इष्टतम समाधान के लिए भुगतान करते हैं, लेकिन वैश्विक दृष्टिकोण से समस्या पर विचार नहीं करते हैं।
नोट: ऊपर दिए गए उदाहरण में, एक अलग प्रारंभिक आवेदक चुनने में मदद नहीं करेगा, क्योंकि ए 4 अभी भी शामिल होगा। शायद पूरी तरह से लालची हो और हमारे पहले आवेदक के रूप में सबसे बड़ी संख्या में कौशल के साथ आवेदक का चयन करें।
यदि कोई ** ** इष्टतम ** समाधान ढूंढने का प्रबंधन करता है जो n^2 में भी चलता है तो मुझे मेरा हटाना खुशी होगी। – Numbers