मान लीजिए हमारे पास nums नामक एक सरणी है, जिसका आकार 2*n है। हमें इस सरणी पर n ऑपरेशन करने हैं। i-वें ऑपरेशन (1-इंडेक्स्ड) में हम निम्न करेंगे:
दो तत्व x और y चुनें।
i * gcd(x, y) का स्कोर प्राप्त करें।
x और y को nums सरणी से हटा दें।
हमें n ऑपरेशन करने के बाद अधिकतम संभव स्कोर ज्ञात करना है।
उदाहरण के लिए, यदि इनपुट nums = [6,2,1,5,4,3] है, तो आउटपुट 14 होगा क्योंकि इष्टतम विकल्प हैं: (1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
n := nums का आकार
dp := (2^n) आकार की एक सरणी जिसे -1 से भरा गया है।
एक फ़ंक्शन dfs() परिभाषित करें जो mask और t लेता है।
यदि mask, (2^n - 1) के बराबर है, तो 0 लौटाएं।
यदि dp[mask] -1 के बराबर नहीं है, तो dp[mask] लौटाएं।
ma := 0
i को 0 से n-1 तक लूप करें:
यदि (2^i) AND mask शून्येतर है, तो अगले इटरेशन पर जाएं।
j को i+1 से n-1 तक लूप करें:
यदि (2^j) AND mask शून्येतर है, तो अगले इटरेशन पर जाएं।
next := dfs(mask OR 2^i OR 2^j, t+1) + gcd(nums[i], nums[j]) * t
ma := next और ma का अधिकतम।
dp[mask] := ma
dp[mask] लौटाएं।
मुख्य विधि से 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
