ปัญหา
ร้านโดนัททำเป็น Batch ขนาด batchSize กลุ่มลูกค้าแต่ละกลุ่มต้องได้รับโดนัทครบก่อนกลุ่มถัดไป ลูกค้าแต่ละคนได้ 1 โดนัท กลุ่มจะ "มีความสุข" (Happy) ถ้าลูกค้าคนแรกได้โดนัทสด (ไม่ใช่เศษจากกลุ่มก่อน) จัดเรียงกลุ่มใหม่เพื่อเพิ่มจำนวนกลุ่ม Happy สูงสุด
ตัวอย่าง
batchSize = 4, groups = [2,1,8,4,3] → Output: 4
จัดเรียง: [8,4,2,3,1] กลุ่มที่ 1-4 Happy
อัลกอริทึม (DP + State Compression)
- แปลง groups เป็น modulo batchSize (เฉพาะเศษสำคัญ)
- นับความถี่แต่ละเศษ → State Vector g[0..batchSize-1]
- DP State: (current_sum_mod, remaining_groups_vector)
- Transition: เลือกกลุ่มเศษ k ที่เหลือ > 0 → New State ((sum+k)%batchSize, g[k]-1)
- Reward: +1 ถ้า New Sum ≡ 0 (เริ่ม Batch ใหม่ = กลุ่มถัดไป Happy)
- Memoization สำหรับ State Space
ตัวอย่างโค้ด
from collections import Counter
def solve(batchSize, groups):
l = [g % batchSize for g in groups]
count = Counter(l)
g = [count[i] for i in range(batchSize)]
from functools import lru_cache
@lru_cache(None)
def dp(sm, t):
if max(t) == 0:
return 0
ans = 0
arr = list(t)
for k in range(batchSize):
if arr[k] == 0:
continue
arr[k] -= 1
ans = max(ans, dp((sm + k) % batchSize, tuple(arr)))
arr[k] += 1
return ans + (sm == 0)
return dp(0, tuple(g))
batchSize = 4
groups = [2,1,8,4,3]
print(solve(batchSize, groups)) # 4ความซับซ้อน
- State Space: batchSize × (Product of (count[i]+1))
- เหมาะกับ batchSize ≤ 9, n ≤ 30
