คำอธิบายปัญหา
กำหนดลิสต์ nums (จำนวนบวก) ดำเนินการ: เลือก a ≤ b ลบทั้งคู่ ถ้า a < b ใส่ b-a กลับ เข้าไป ทำซ้ำได้ไม่จำกัด หา **เลขที่เหลือน้อยที่สุด** (ลิสต์ว่าง = 0)
ตัวอย่าง
nums = [2, 4, 5] → Output: 1
เลือก 4,5 → ใส่ 1 → [2,1] | เลือก 2,1 → ใส่ 1 → [1]
ขั้นตอนการแก้ปัญหา (Subset Sum / Partition)
ปัญหานี้เทียบเท่าการหา **ความต่างน้อยที่สุด** ระหว่างผลรวมสอง subset (Partition Problem)
s = sum(nums)- หา subset sum ใกล้
s/2มากที่สุด → ความต่าง =s - 2*subset_sum - DP เรียกซ้ำ:
f(i, s)= ค่าที่เหลือจาก index i ด้วย sum ปัจจุบัน s
การตนการทำงาน (Python)
def solve(nums):
s = sum(nums)
def f(i, s):
if i >= len(nums):
return s
n = nums[i]
if s - 2 * n < 0:
return f(i + 1, s)
return min(f(i + 1, s - 2 * n), f(i + 1, s))
return f(0, s)
nums = [2, 4, 5]
print(solve(nums)) # Output: 1
หมายเหตุ
- วิธีนี้เป็น exponential time สำหรับ n ใหญ่ควรใช้ DP bottom-up หรือ bitset
- หลักการคือ: การดำเนินการนี้คง "ความต่าง modulo 2" และเทียบเท่า partition problem
