ধরুন আমাদের nums নামে একটি অ্যারে আছে, যার আকার 2*n। আমাদের এই অ্যারেতে n অপারেশন করতে হবে। ith অপারেশনে (1-সূচিবদ্ধ), আমরা নিম্নলিখিতগুলি করব:
-
দুটি উপাদান নির্বাচন করুন, x এবং y।
-
i*gcd(x, y) এর একটি স্কোর পান।
-
অ্যারে সংখ্যা থেকে x এবং y সরান।
n অপারেশন করার পর আমাদের সর্বোচ্চ স্কোর খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[6,2,1,5,4,3], তাহলে আউটপুট 14 হবে কারণ সর্বোত্তম পছন্দগুলি হল (1 * gcd(1, 5)) + (2 * gcd( 2, 4)) + (3 * gcd(3, 6)) =1 + 4 + 9 =14
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=সংখ্যার আকার
-
dp :=আকারের একটি অ্যারে (2^n) এবং -1
দিয়ে পূরণ করুন -
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি মাস্ক লাগবে, t
-
যদি মাস্ক (2^n - 1) এর মত হয়, তাহলে
-
রিটার্ন 0
-
-
যদি dp[মাস্ক] -1 এর মত না হয়, তাহলে
-
dp[মাস্ক]
ফেরত দিন
-
-
ma :=0
-
0 থেকে n রেঞ্জের জন্য, করুন
-
যদি 2^i এবং মুখোশ অ-শূন্য হয়, তাহলে
-
পরবর্তী পুনরাবৃত্তির জন্য যান
-
-
i + 1 থেকে n - 1 পর্যন্ত j-এর জন্য, করুন
-
যদি 2^j এবং মুখোশ অ-শূন্য হয়, তাহলে
-
পরবর্তী পুনরাবৃত্তির জন্য যান
-
-
পরবর্তী :=dfs(মাস্ক বা 2^i বা 2^j, t+1) + gcd(nums[i], nums[j])*t
-
ma :=পরের সর্বোচ্চ এবং ma
-
-
-
dp[মাস্ক] :=মা
-
dp[মাস্ক]
ফেরত দিন -
প্রধান পদ্ধতি থেকে, 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
