โปรแกรมตรวจสอบว่าขโมยสามารถขโมยห้องเซฟได้หรือไม่ใน Python

มีขโมย N คน แต่ละคนใช้เวลา time[i] ในห้องเซฟ ประตูมีเจ้าหน้าที่คุ้มครอง กลับมาในเวลา G ได้มีคนในห้องเซฟพร้อมกันสูงสุด 2 คน ตรวจสอบว่าขโมยทุกคนสามารถเข้าไปและออกมาได้ก่อนเจ้าหน้าที่กลับ

ตัวอย่าง: N=3, G=5, time=[3,5,2] → True (จัดตารางได้)

ขั้นตอนการแก้ปัญหา

1. หาก sum(time) > 2G → False
2. หาก sum(time) ≤ G → True
3. มิฉะนั้น ใช้ Subset Sum DP (knapsack) หาผลรวมที่ทำได้ไม่เกิน G:
   • valid[0]=True
   • สำหรับแต่ละ time x: อัปเดต valid แบบ 0/1 knapsack
   • หา max i ที่ valid[i] True → sum(time) - max_i ≤ G ? True : False

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

def solve(N, G, time):
    total = sum(time)
    if total > 2 * G:
        return False
    if total <= G:
        return True
    valid = [False] * (G + 1)
    valid[0] = True
    for x in time:
        for i in range(G, -1, -1):
            if i - x >= 0 and valid[i - x]:
                valid[i] = True
    max_i = max(i for i, v in enumerate(valid) if v)
    return total - max_i <= G

# ทดสอบ
N = 3
G = 5
time = [3, 5, 2]
print(solve(N, G, time))  # ผลลัพธ์: True

อินพุตตัวอย่าง

3,5,[3,5,2]

เอาต์พุตตัวอย่าง

True