Filling Bookcase Shelves: จัดหนังสือบนชั้นให้ความสูงรวมต่ำสุด

โจทย์

มีหนังสือลำดับ books[i] = [thickness, height] วางบนชั้นกว้าง shelf_width ต้องวางตามลำดับ เลือกหนังสือต่อเนื่องๆ วางบนชั้นเดียวกัน (ผลรวม thickness ≤ shelf_width) ความสูงชั้น = max height ของหนังสือบนชั้นนั้น หา Minimum Total Height ของตู้หนังสือทั้งหมด

ตัวอย่าง: books=[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width=4 → 6 (ชั้น 1: 1+3, ชั้น 2: 3, ชั้น 3: 2)

อัลกอริทึม: Dynamic Programming (DP)

dp[i] = min total height สำหรับหนังสือ 0..i

• Base: dp[0] = books[0][1]
• Transition: สำหรับ i, ลองวางหนังสือ j..i บนชั้นเดียวกัน (backward):
  • Track curr_width และ curr_max_height
  • ถ้า curr_width ≤ shelf_width: dp[i] = min(dp[i], curr_max_height + (dp[j-1] if j>0 else 0))

การติดตั้ง (Python Implementation)

class Solution:
    def minHeightShelves(self, books: list[list[int]], shelf_width: int) -> int:
        n = len(books)
        dp = [float('inf')] * n
        dp[0] = books[0][1]
        
        for i in range(1, n):
            curr_width = 0
            curr_max_height = 0
            # ลองวางหนังสือ j..i บนชั้นเดียวกัน (backward)
            for j in range(i, -1, -1):
                curr_width += books[j][0]
                if curr_width > shelf_width:
                    break
                curr_max_height = max(curr_max_height, books[j][1])
                prev_height = dp[j-1] if j > 0 else 0
                dp[i] = min(dp[i], prev_height + curr_max_height)
        
        return dp[-1]

# ทดสอบ
ob = Solution()
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
print(ob.minHeightShelves(books, 4))  # 6

# ทดสอบเพิ่ม
print(ob.minHeightShelves([[1,3],[2,4],[3,2]], 6))  # 4 (all on one shelf)

Output

6
4

การทำงานทีละขั้น (ตัวอย่าง)

books:     [1,1] [2,3] [2,3] [1,1] [1,1] [1,1] [1,2]
index:       0     1     2     3     4     5     6
width:       1     2     2     1     1     1     1
height:      1     3     3     1     1     1     2

dp[0] = 1
dp[1]: j=1: w=2,h=3 → 3; j=0: w=3,h=3 → 3 → dp[1]=3
dp[2]: j=2: w=2,h=3 → 3+dp[1]=6; j=1: w=4,h=3 → 3+dp[0]=4; j=0: w=5>4 break → dp[2]=4
dp[3]: j=3: w=1,h=1 → 1+dp[2]=5; j=2: w=3,h=3 → 3+dp[1]=6; j=1: w=5>4 break → dp[3]=5
dp[4]: j=4: w=1,h=1 → 1+dp[3]=6; j=3: w=2,h=1 → 1+dp[2]=5; j=2: w=4,h=3 → 3+dp[1]=6 → dp[4]=5
dp[5]: ... → dp[5]=5
dp[6]: j=6: w=1,h=2 → 2+dp[5]=7; j=5: w=2,h=2 → 2+dp[4]=7; j=4: w=3,h=2 → 2+dp[3]=7; j=3: w=4,h=2 → 2+dp[2]=6 → dp[6]=6

Answer: 6

Complexity

• Time: O(n²) - nested loop (n ≤ 1000 ตาม constraint ทั่วไป)
• Space: O(n) - dp array

สรุป

Filling Bookcase Shelves เป็น DP บน sequence: dp[i] = min height จนถึงหนังสือ i ลองจัดกลุ่มหนังสือท้ายเป็นชั้นเดียวกัน (backward) ใช้ running width/height คำนวณได้ O(n²)

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ