पायथन में एक गेम में संग्रहणीय अधिकतम अंक खोजने का कार्यक्रम

मान लीजिए हम ताश का खेल खेल रहे हैं। हमें कई कार्ड दिए गए हैं जिनमें से प्रत्येक पर एक संख्या के साथ रैखिक रूप से व्यवस्थित किया गया है। कार्ड पर नंबर बेतरतीब ढंग से वितरित किए जाते हैं; और कार्ड की शुरुआत और अंत में, उन पर नंबर 1 के साथ दो कार्ड डाले जाते हैं। अब, खेल में, हमें दिए गए कार्डों को उठाकर अधिकतम अंक एकत्र करने हैं। कार्ड एक सरणी 'कार्ड' में प्रस्तुत किए जाते हैं जहां सरणी में तत्व कार्ड की संख्या का प्रतिनिधित्व करते हैं [i]। जब हम कार्ड i उठाते हैं, तो हम अंक कार्ड [i - 1] * कार्ड [i] * कार्ड [i + 1] एकत्र करते हैं। जब हम एक कार्ड उठाते हैं, कार्ड [i - 1] और कार्ड [i] पड़ोसी बन जाते हैं। इसलिए, इन दिए गए कार्डों से हम अधिकतम अंक प्राप्त कर सकते हैं जो हम एकत्र कर सकते हैं।

इसलिए, यदि इनपुट कार्ड की तरह है =[7, 5, 9, 10], तो आउटपुट 1025

होगा।

तो खेल में, हम उठा सकते हैं -

इंडेक्स 1 पर कार्ड और 7 * 5 * 9 =315 अंक प्राप्त करें।

नए इंडेक्स 1 पर कार्ड और 7 * 9 * 10 =630 अंक प्राप्त करें।

इंडेक्स 1 पर कार्ड और 7 * 10 =70 अंक प्राप्त करें।

अंतिम कार्ड और 10 अंक प्राप्त करें।

कुल अंक =315 + 630 + 70 + 10 =1025

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

फ़ंक्शन को परिभाषित करें search() । इसमें x, y
- अस्थायी:=0
- z के लिए x + 1 से y की श्रेणी में, करें
  - अस्थायी:=अधिकतम (अस्थायी, खोज(x, z) + खोज(z, y) + कार्ड[x] * कार्ड[z] * कार्ड[y])
- वापसी का तापमान
सूची कार्ड के आरंभ और अंत में क्रमशः 1 और 1 मान डालें
वापसी खोज(0, कार्ड का आकार -1)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(cards):
   def search(x, y):
      temp = 0
      for z in range(x + 1, y):
         temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
      return temp
   cards = [1] + cards + [1]
   return search(0, len(cards) - 1)

print(solve([7, 5, 9, 10]))

इनपुट

[7, 5, 9, 10]