โปรแกรมหาต้นทุนน้อยที่สุดในการรวมลิสต์ให้เหลือตัวเลขเดียวใน Python

สมมติว่าเรามีรายการตัวเลข nums เราสามารถลดความยาวได้โดยเลือก 2 ตัว นำออก และต่อผลรวมท้ายรายการ ต้นทุนคือผลรวมของสองตัวที่นำออก หาต้นทุนรวมน้อยที่สุดจนเหลือ 1 ตัว

ตัวอย่าง: nums = [2, 3, 4, 5, 6] ผลลัพธ์ 45 (2+3=5, 4+5=9, 6+5=11, 9+11=20, รวม 5+9+11+20=45)

ขั้นตอนการแก้ปัญหา (Min Heap / Huffman Coding Idea)

1. สร้าง Min Heap จาก nums
2. ans = 0
3. วนลูป while len(nums) >= 2:
   • a = heappop(nums), b = heappop(nums)
   • ans += a + b
   • heappush(nums, a + b)
4. คืนค่า ans

ตัวอย่างโค้ด Python

import heapq

class Solution:
    def solve(self, nums):
        heapq.heapify(nums)
        ans = 0
        while len(nums) >= 2:
            a = heapq.heappop(nums)
            b = heapq.heappop(nums)
            ans += a + b
            heapq.heappush(nums, a + b)
        return ans

ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))  # Output: 45

อินพุต / เอาต์พุต

Input: [2, 3, 4, 5, 6]

Output: 45