मान लीजिए कि हमारे पास nums नामक एक सरणी है, जिसका आकार 2*n है। हमें इस ऐरे पर n ऑपरेशन करना है। Ith ऑपरेशन (1-अनुक्रमित) में, हम निम्नलिखित कार्य करेंगे:
-
दो तत्वों, x और y का चयन करें।
-
i*gcd(x, y) का स्कोर प्राप्त करें।
-
सरणी अंकों से x और y निकालें।
हमें n ऑपरेशन करने के बाद अधिकतम अंक प्राप्त करने होंगे।
इसलिए, यदि इनपुट nums =[6,2,1,5,4,3] जैसा है, तो आउटपुट 14 होगा क्योंकि इष्टतम विकल्प हैं (1 * gcd(1, 5)) + (2 * gcd( 2, 4)) + (3 * जीसीडी(3, 6)) =1 + 4 + 9 =14
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=अंकों का आकार
-
dp:=आकार की एक सरणी (2^n) और -1 से भरें
-
फ़ंक्शन को परिभाषित करें dfs() । यह मुखौटा ले जाएगा, टी
-
अगर मास्क (2^n-1) जैसा ही है, तो
-
वापसी 0
-
-
अगर dp[mask] -1 के समान नहीं है, तो
-
वापसी डीपी [मुखौटा]
-
-
मा:=0
-
मेरे लिए 0 से n की सीमा में, करें
-
अगर 2^i और मास्क गैर-शून्य है, तो
-
अगले पुनरावृत्ति के लिए जाएं
-
-
j के लिए i + 1 से n-1 की श्रेणी में, करें
-
अगर 2^j और मास्क गैर-शून्य है, तो
-
अगले पुनरावृत्ति के लिए जाएं
-
-
अगला:=dfs(मुखौटा या 2^i या 2^j, t+1) + gcd(nums[i], nums[j])*t
-
मा :=अधिकतम अगले और मा
-
-
-
डीपी [मुखौटा]:=मा
-
वापसी डीपी [मुखौटा]
-
मुख्य विधि से, वापस dfs(0, 1)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें
from math import gcd def solve(nums): n = len(nums) dp = [-1] * (1 << n) def dfs(mask, t): if mask == (1 << n) - 1: return 0 if dp[mask] != -1: return dp[mask] ma = 0 for i in range(n): if (1 << i) & mask: continue for j in range(i + 1, n): if (1 << j) & mask: continue next = dfs(mask | (1 << i) | (1 << j), t + 1) + gcd(nums[i], nums[j]) * t ma = max(next, ma) dp[mask] = ma return dp[mask] return dfs(0, 1) nums = [6,2,1,5,4,3] print(solve(nums))
इनपुट
[6,2,1,5,4,3]
आउटपुट
14