মনে করুন nums নামে একটি অ্যারে আছে যার আকার 2*n। আমাদের এই অ্যারেতে n অপারেশন করতে হবে। i-তম অপারেশনে (1-ইন্ডেক্সড), আমরা নিচের কাজগুলো করব −
দুটি এলিমেন্ট, x এবং y সিলেক্ট করুন।
i*gcd(x, y) স্কোর পান।
nums অ্যারে থেকে x এবং y সরিয়ে দিন।
আমাদের 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) & mask নন-জিরো হয়, তবে
পরবর্তী ইটারেশনে যান
j = i+1 থেকে n-1 পর্যন্ত জন্য, করুন
যদি (2^j) & mask নন-জিরো হয়, তবে
পরবর্তী ইটারেশনে যান
next := dfs(mask | (2^i) | (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
