โปรแกรมค้นหาคะแนนสูงสุดหลังจากการดำเนินการ n ใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า 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 * gcd(3, 6)) =1 + 4 + 9 =14

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums

• dp :=อาร์เรย์ขนาด (2^n) และเติมด้วย -1

• กำหนดฟังก์ชัน dfs() นี่จะเอาหน้ากาก t

• ถ้าหน้ากากเหมือนกับ (2^n - 1) แล้ว

  • คืนค่า 0

• ถ้า dp[mask] ไม่เหมือนกับ -1 แล้ว

  • ส่งคืน dp[หน้ากาก]

• แม่ :=0

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • ถ้า 2^i AND mask ไม่ใช่ศูนย์ ดังนั้น

    • ไปทำซ้ำต่อไป

  • สำหรับ j ในช่วง i + 1 ถึง n - 1 ทำ

    • ถ้า 2^j และ mask ไม่ใช่ศูนย์ ดังนั้น

      • ไปทำซ้ำต่อไป

    • ต่อไป :=dfs(mask OR 2^i OR 2^j, t+1) + gcd(nums[i], nums[j])*t

    • ma :=สูงสุดของ next และ ma

• dp[mask] :=ma

• ส่งคืน 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