फेसबुक साक्षात्कार: उस ऑर्डर को ढूंढें जो एक अंगूठी में संख्या के साथ बॉक्स का चयन करके अधिकतम योग देता है, जब उसके आगे के दो नष्ट हो जाते हैं

Question

इस बारे में कोई समान प्रश्न नहीं मिला। यह एक अंतिम दौर फेसबुक प्रश्न है:

आपको बक्से की अंगूठी दी गई है। प्रत्येक बॉक्स में गैर-ऋणात्मक संख्या होती है, डुप्लिकेट हो सकती है।

एक फ़ंक्शन/एल्गोरिदम लिखें जो आपको वह ऑर्डर देगा जिसमें आप बॉक्स चुनते हैं, जो आपको अधिकतम योग देगा।

कैच है, यदि आप एक बॉक्स का चयन करते हैं, तो इसे अंगूठी से हटा दिया जाता है, और इसके आगे के दो बक्से भी हैं (दाईं ओर और आपके द्वारा चुने गए बाईं ओर)।

इसलिए यदि मैं की
{10 3 से 8 12}

अगर मैं चयन 12, 8 और 10 नष्ट हो जाएगा और आप 3.

अधिकतम के साथ छोड़ दिया जाता है का चयन किया जाएगा एक अंगूठी है 8 पहले 10, या 10 पहले 8. 8.

मैंने बॉक्स को अपना मूल्य ले कर अपने मूल्य को फिर से असाइन करने का प्रयास किया और फिर लागत के रूप में अगले दो को घटा दिया।

तो पुराने अंगूठी है {10 3 से 8 12}

नई अंगूठी है {-5, -15, -7, -6}, और मैं उच्चतम ले जाएगा।

बहरहाल, यह निश्चित रूप से अगर आपके पास काम नहीं करता {10, 19, 10, 0}, आपके पास दो 10s लगने चाहिए, लेकिन एल्गोरिथ्म 19 और 0.

सहायता ले जाएगा कृपया?

यह गतिशील प्रोग्रामिंग की संभावना है, लेकिन मुझे नहीं पता कि कैसे।

अंगूठी किसी भी आकार का हो सकता है।

Answer 1

यहाँ कुछ अजगर कि समस्या का हल है:

def sublist(i,l): 
    if i == 0: 
     return l[2:-1] 
    elif i == len(l)-1: 
     return l[1:-2] 
    else: 
     return l[0:i-1] + l[i+2:] 

def val(l): 
    if len(l) <= 3: 
     return max(l) 
    else: 
     return max([v+val(m) for v,m in [(l[u],sublist(u,l)) for u in range(len(l))]]) 

def print_indices(l): 
    print("Total:",val(l)) 
    while l: 
     vals = [v+val(m) for v,m in [(l[u],sublist(u,l)) for u in range(len(l)) if sublist(u,l)]] 
     if vals: 
      i = vals.index(max(vals)) 
     else: 
      i = l.index(max(l)) 
     print('choice:',l[i],'index:',i,'new list:',sublist(i,l)) 
     l = sublist(i,l) 

print_indices([10,3,8,12]) 
print_indices([10,19,10,0]) 

आउटपुट:

कुल: 18
चुनाव: 10 सूचकांक: 0 नई सूची [8]
विकल्प: 8 सूचकांक: 0 नई सूची: []

कुल: 20
चुनाव: 10 सूचकांक: 0 नई सूची [10]
चुनाव: 10 सूचकांक: 0 नई सूची: []

कोई संदेह नहीं है यह थोड़ा अनुकूलित किया जा सकता है। कुंजी बिट val() है, जो किसी दिए गए अंगूठी के कुल मूल्य की गणना करता है। बाकी बस बहीखाता है।