โจทย์
มี packages น้ำหนัก weights[i] ส่งภายใน D วัน ทุกวันบรรทุกตามลำดับ (contiguous) ไม่เกินความจุ capacity หา Minimum Capacity ที่ส่งครบภายใน D วัน
ตัวอย่าง: weights=[3,2,2,4,1,4], D=3 → Capacity=6 (Day1: 3+2, Day2: 2+4, Day3: 1+4)
อัลกอริทึม: Binary Search on Answer + Greedy Check
Search Space: low = max(weights) (ต้องบรรทุกของหนักสุดได้), high = sum(weights) (บรรทุกทั้งหมด 1 วัน)
Check Function: กำหนด capacity, จำลองการบรรทุกวันต่อวัน (greedy ใส่เท่าที่จะใส่ได้) นับวัน → ≤ D?
การติดตั้ง (Python Implementation)
class Solution:
def shipWithinDays(self, weights: list[int], days: int) -> int:
def can_ship(capacity: int) -> bool:
"""ตรวจสอบว่า capacity นี้ ส่งครบภายใน days วันได้ไหม"""
d = 1
current_load = 0
for w in weights:
if current_load + w > capacity:
d += 1
current_load = w
if d > days:
return False
else:
current_load += w
return True
low = max(weights)
high = sum(weights)
while low < high:
mid = (low + high) // 2
if can_ship(mid):
high = mid
else:
low = mid + 1
return low
# ทดสอบ
ob = Solution()
print(ob.shipWithinDays([3,2,2,4,1,4], 3)) # 6
print(ob.shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(ob.shipWithinDays([1,2,3,1,1], 4)) # 3
Output
6 15 3
การทำงาน Binary Search (ตัวอย่างแรก)
weights=[3,2,2,4,1,4], D=3 low=4, high=16 mid=10: can_ship? Day1:3+2+2+4=11>10→Day1:3+2+2=7, Day2:4+1+4=9 → 2 days ≤3 ✓ → high=10 mid=7: Day1:3+2+2=7, Day2:4+1=5, Day3:4 → 3 days ≤3 ✓ → high=7 mid=5: Day1:3+2=5, Day2:2+4=6>5→Day2:2, Day3:4+1=5, Day4:4 → 4 days >3 ✗ → low=6 mid=6: Day1:3+2=5, Day2:2+4=6, Day3:1+4=5 → 3 days ≤3 ✓ → high=6 low=6, high=6 → return 6
Complexity
- Time: O(n log(sum(weights))) - Binary search × O(n) check
- Space: O(1)
สรุป
Capacity To Ship Packages Within D Days เป็นโจทย์ Binary Search on Answer คลาสสิก Check function ใช้ Greedy simulation การบรรทุกวันต่อวัน
หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ
