सिक्का परिवर्तन: लालची दृष्टिकोण

Question

समस्या क्वार्टर, डाइम्स, निकल और पेनीज़ के साथ एन सेंट बदल रही है, और कम से कम कुल सिक्कों का उपयोग कर रही है। विशेष मामले में जहां चार संप्रदाय क्वार्टर, डाइम्स, निकल और पेनीज़ हैं, हमारे पास सी 1 = 25, सी 2 = 10, सी 3 = 5, और सी 4 = 1.

यदि हमारे पास केवल क्वार्टर, डाइम्स, और पैसे (और कोई nickels) उपयोग करने के लिए, हम तीन सिक्के, अर्थात्, तीन ऑफ डाइम्स का इस्तेमाल किया है सकते थे, जबकि पैसे-लालची एल्गोरिथ्म छह सिक्के -एक तिमाही और पांच का उपयोग कर 30 सेंट के लिए परिवर्तन होगा।

संप्रदायों के एक सेट को देखते हुए, हम कैसे कह सकते हैं कि लालची दृष्टिकोण एक इष्टतम समाधान बनाता है या नहीं?

Answer 1

आप जो पूछ रहे हैं वह यह तय करना है कि परिवर्तन की समस्या के लिए सिक्कों की एक दी गई प्रणाली कैननिकल है या नहीं। एक प्रणाली कैनोलिक है यदि लालची एल्गोरिदम हमेशा एक इष्टतम समाधान देता है। आप तय कर सकते हैं कि सिक्कों की एक प्रणाली जिसमें 1 प्रतिशत टुकड़ा शामिल है, कैनोनिकल है या सीमित चरणों में नहीं है। विवरण, और कुछ मामलों में अधिक कुशल एल्गोरिदम, http://arxiv.org/pdf/0809.0400.pdf में पाया जा सकता है।