ปัญหา
อาร์เรย์ nums ขนาด 2n ทำ n Operations: Operation i (1-indexed) เลือก x,y ได้คะแนน i × gcd(x,y) นำ x,y ออก หาคะแนนสูงสุด
ตัวอย่าง
nums = [6,2,1,5,4,3] → Output: 14
Optimal: 1×gcd(1,5) + 2×gcd(2,4) + 3×gcd(3,6) = 1+4+9=14
อัลกอริทึม (DP + Bitmask)
- State: Bitmask ของตัวเลขที่ใช้แล้ว (2n ≤ 14 → 2^14 = 16384 States)
- DP[mask] = คะแนนสูงสุดจาก State นี้
- Transition: เลือกคู่ (i,j) ที่ยังไม่ได้ใช้ → New Mask = mask | (1<
- Operation Number = Popcount(mask)/2 + 1
- Recursive DFS + Memoization
ตัวอย่างโค้ด
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_score = dfs(mask | (1 << i) | (1 << j), t + 1) + gcd(nums[i], nums[j]) * t
ma = max(next_score, ma)
dp[mask] = ma
return dp[mask]
return dfs(0, 1)
nums = [6,2,1,5,4,3]
print(solve(nums)) # 14ความซับซ้อน
- Time: O(n² × 2^n) สำหรับ n ≤ 7 (2n ≤ 14) ใช้ได้
- Space: O(2^n)
