न्यूनतम सिक्का परिवर्तन समस्या एक एनपी-पूर्ण है समस्या लेकिन सिक्कों के कुछ सेटों के लिए लालची एल्गोरिथ्म (पहले सबसे बड़ा मूल्यवर्ग चुनें) काम करता है। सिक्का-मूल्यों को दर्शाने वाले पूर्णांकों के एक सेट को देखते हुए, यह निर्धारित करने के लिए सबसे तेज़ एल्गोरिदम क्या है कि लालची एल्गोरिदम पर्याप्त है या नहीं? एक स्पष्ट तरीका यह है कि सबसे बड़े मूल्यवर्ग तक अपने गतिशील प्रोग्रामिंग समाधान का निर्माण करें और प्रत्येक के लिए देखें कि क्या यह लालची तरीके से बेहतर समाधान देता है। लेकिन क्या इसका पता लगाने का कोई तेज़ "गणित-मार्ग" है?

8
pathikrit 17 मई 2011, 04:45

4 जवाब

सबसे बढ़िया उत्तर

लालची एल्गोरिदम काम करेगा यदि निम्नलिखित चयन लक्ष्य राशि उत्पन्न करता है: (अधिक जटिल प्रारूप हो सकते हैं जो काम करेंगे, लेकिन यह जांच करने के लिए सरल और रैखिक है)

मान लीजिए 1 चयनित का प्रतिनिधित्व करते हैं। सेट, सबसे बड़े मूल्यवर्ग से, ऐसा दिखेगा:

11...1100...00100...00

यानी, सबसे बड़े से शून्य या अधिक चयनित, और एक अन्य तत्व चयनित।

यह इष्टतम क्यों है यह साबित करना आसान है। C = s तत्वों को सबसे बड़े से चुने जाने दें, तो हम जानते हैं कि C किसी भी s या उससे कम तत्वों के लिए सबसे बड़ा संभव योग उत्पन्न करता है, क्योंकि, यदि आप C में किसी तत्व को प्रतिस्थापित करना चाहते हैं, तो आपको ऐसा निम्न के साथ करना होगा- मूल्यवान तत्व, चूंकि सबसे बड़े तत्व पहले ही चुने जा चुके हैं (और हटाने से लागत में भी कमी आएगी)। चूंकि सी लक्ष्य से कम मूल्य उत्पन्न करता है (क्योंकि उस एक अन्य तत्व की आवश्यकता होती है), हमें लक्ष्य तक पहुंचने के लिए कम से कम एक अन्य तत्व की आवश्यकता होती है, इस प्रकार लक्ष्य तक पहुंचने के लिए आवश्यक तत्वों की न्यूनतम मात्रा s+1 है, जो प्रमाण समाप्त करता है।

इसका मूल्यांकन करने के लिए आपको ओ (एन) की आवश्यकता है, और यह निम्नानुसार किया जा सकता है: (जावा में)

int[] sortedCoins = ...;
int sum = 0, selectionCount = 0, i = 0;
for (; i < sortedCoins.length; i++)
{
  sum += sortedCoins[i];
  if (sum >= target) break;
  selectionCount++;
}
sum -= sortedCoins[i]; // we added the element to push us over, so remove it again
for (; i < sortedCoins.length; i++)
{
  if (sum + sortedCoins[i] == target)
    return selectionCount+1;
}
return -1; // not found

ओह, और एक मामूली मामला भी है जहां लक्ष्य = 0 जिसे जांचने की आवश्यकता है कि इसकी अनुमति है या नहीं।

उपरोक्त के लिए एक लक्ष्य राशि की आवश्यकता होती है, यदि आप कई लक्ष्य राशियों की जांच करना चाहते हैं, तो आप संभवतः उपरोक्त विधि के साथ ओ (एन ^ 2) में सभी संभावित रकम उत्पन्न कर सकते हैं और गणना के लिए योग का नक्शा रख सकते हैं और बस एक लुकअप कर सकते हैं मूल्य प्राप्त करें यदि यह मौजूद है।

संपादित करें: शाखा और बाध्य

उपरोक्त के विस्तार और डीपी के विकल्प के रूप में, मैं सुझाव देता हूं कि क्रूर बल को शाखा और बाध्य के साथ लालच से संसाधित किया जाए। ऊपर के समान तर्क का उपयोग करते हुए, आप जानते हैं कि यदि bestCoins का मान और (currentSum + (bestCoins - currentCoins) * currentItem.value) < target है, तो आप वर्तमान पथ को छोड़ सकते हैं।

ध्यान दें कि यह कुछ समस्याओं पर बुरी तरह विफल हो सकता है और दूसरों पर आश्चर्यजनक रूप से काम कर सकता है (मुझे लगता है कि यह काफी हद तक इस बात पर निर्भर करता है कि हम कितनी जल्दी एक अच्छा समाधान ढूंढते हैं)। हमेशा के लिए लेने से बचने के लिए, आप इष्टतम समाधान में सिक्कों की न्यूनतम संभव संख्या को स्टोर कर सकते हैं (पहले तत्वों को देखने से प्राप्त जब तक हम लक्ष्य तक नहीं पहुंचते, ऊपर के समान), और इससे दूर के रास्ते काट सकते हैं।

यदि सही किया जाता है, तो आप इसे थोड़े समय के लिए चलाने में सक्षम होना चाहिए, और यदि यह पूरा हो गया है और हमारे पास समाधान है, तो हमारे पास इष्टतम समाधान है, यदि नहीं, तो हमने बहुत अधिक समय नहीं गंवाया और एक और एल्गोरिदम चला सकते हैं डीपी की तरह।

0
Bernhard Barker 5 जिंदा 2013, 21:25

मैं हाल ही में 1 समाधान के साथ आया था जो यह दिखाता था कि दी गई 2 शर्तें संतुष्ट हैं, लालची एल्गोरिदम इष्टतम समाधान उत्पन्न करेगा।

A) G.C.D (1 को छोड़कर सभी संप्रदाय) = दूसरा सबसे छोटा मूल्यवर्ग।

बी) किसी भी 2 लगातार मूल्यवर्ग का योग लगातार तीसरे मूल्यवर्ग से कम होना चाहिए।

उदाहरण के लिए। सी 2 + सी 3 <सी 4।

(जहाँ c1 = 1; c2, c3, c4 आरोही क्रम में सिक्का मूल्यवर्ग हैं)।

मैं समझता हूं कि यह संपूर्ण समाधान नहीं है। हालांकि, मेरा मानना ​​है कि अगर इन 2 शर्तों को पूरा किया जाता है, तो लालची एल्गोरिदम इष्टतम समाधान देगा।

1
Prashant Vaidyanathan 6 मार्च 2013, 10:23

पियर्सन का पेपर बदलाव के लिए एक बहुपद-समय एल्गोरिथ्म समस्या ऑपरेशन रिसर्च लेटर्स 33:3 (मई 2005), पीपी 231-234 लालची एल्गोरिथम (यदि यह मौजूद है) के लिए न्यूनतम प्रति-उदाहरण खोजने के लिए एक बहुपद समय एल्गोरिथ्म देता है। किसी विस्तृत खोज की आवश्यकता नहीं है, उनका मुख्य प्रमेय उम्मीदवारों के समूह को बहुत कम कर देता है।

0
vonbrand 19 जिंदा 2021, 18:54

लालची समाधान परिवर्तन करने के लिए निश्चित राशि के संबंध में केवल कुछ संप्रदायों के लिए काम करता है।

एक बैकट्रैकिंग कदम जब जोड़ा जाता है, तो यह अब लालची नहीं है, और यह अंततः, एक सभी संभावित समाधान ढूंढता है, और इसलिए यह न तो एक गतिशील प्रोग्रामिंग समस्या है।

उदाहरण: सिक्का = [2, 5] पर विचार करें, और बदली जाने वाली राशि 16 है। एक लालची पहला समाधान स्वाभाविक रूप से पहले सबसे बड़े मूल्यवर्ग की तलाश में है, [5, 5, 5] और फिर यह 1 पर अटक गया। एक बैकट्रैकिंग कदम एक और समाधान देता है [5, 5, 2, 2, 2]।

-4
hsheboul 1 जुलाई 2011, 07:55