elevator_rides

Bài toán: $4$ người có cân nặng $[3, 5, 2, 7]$, thang máy sức chứa $x = 8$. Tìm số chuyến ít nhất. Ta dùng QHĐ bitmask với $16$ mask, mỗi mask biểu diễn tập con người đã được chở. $dp[mask]$ lưu (số chuyến tối thiểu, sức chứa còn lại tối đa trong chuyến cuối).

Trường hợp cơ sở: $dp[0] = (1, 8)$. Chưa chở ai. Ta có $1$ chuyến mở sẵn với đầy đủ sức chứa $8$. Mask $0$ = nhị phân $0000$ nghĩa là chưa chọn ai.

Thử thêm người $0$ (nặng $3$) vào mask $0000$. Cân nặng $3 \leq 8$ còn lại, vừa chuyến hiện tại. $dp[0001] = (1, 8-3) = (1, 5)$. Một chuyến, còn trống $5$.

Thêm người $1$ (nặng $5$) vào mask $0000$. Cân nặng $5 \leq 8$, vừa. $dp[0010] = (1, 8-5) = (1, 3)$. Một chuyến, còn trống $3$.

Thêm người $2$ (nặng $2$) vào mask $0000$. Cân nặng $2 \leq 8$, vừa. $dp[0100] = (1, 8-2) = (1, 6)$.

Thêm người $3$ (nặng $7$) vào mask $0000$. Cân nặng $7 \leq 8$, vừa. $dp[1000] = (1, 8-7) = (1, 1)$. Đã tính xong tất cả trạng thái một người từ tập rỗng.

Xử lý mask $0001 = (1,5)$. Thêm người $1$ (nặng $5$). $5 \leq 5$ còn lại, vừa đủ! $dp[0011] = (1, 5-5) = (1, 0)$. Người $0$ và $1$ chung một chuyến, vừa khít sức chứa $3+5=8$.

Từ mask $0001 = (1,5)$, thêm người $2$ (nặng $2$). $2 \leq 5$, vừa. $dp[0101] = (1, 5-2) = (1, 3)$. Người $0$ và $2$ chung chuyến (nặng $3+2=5$).

Từ mask $0001 = (1,5)$, thêm người $3$ (nặng $7$). $7 > 5$ còn lại – không vừa! Mở chuyến mới. $dp[1001] = (1+1, 8-7) = (2, 1)$. Bây giờ cần $2$ chuyến.

Từ mask $0010 = (1,3)$, thêm người $2$ (nặng $2$). $2 \leq 3$, vừa. $dp[0110] = (1, 3-2) = (1, 1)$. Người $1$ và $2$ chung chuyến (nặng $5+2=7$).

Từ mask $0010 = (1,3)$, thêm người $3$ (nặng $7$). $7 > 3$, mở chuyến mới. $dp[1010] = (2, 8-7) = (2, 1)$. Người $1$ và $3$ mỗi người cần chuyến riêng.

Từ mask $0100 = (1,6)$, thêm người $3$ (nặng $7$). $7 > 6$, mở chuyến mới. $dp[1100] = (2, 1)$. Lưu ý: cũng có thể đến từ mask $1000$+người $2$ cho kết quả $(2, 6)$ tốt hơn – ta sẽ cập nhật ngay sau.

Cập nhật! Từ mask $1000 = (1,1)$, thêm người $2$ (nặng $2$). $2 > 1$, mở chuyến mới. Ứng viên $= (2, 8-2) = (2, 6)$. Vì $6 > 1$ sức chứa còn lại và cùng số chuyến, $dp[1100]$ cập nhật thành $(2, 6)$. Còn nhiều chỗ trống hơn nghĩa là còn chỗ cho người tiếp theo.

Từ mask $0011 = (1,0)$, thêm người $2$ (nặng $2$). $2 > 0$, mở chuyến mới. $dp[0111] = (2, 8-2) = (2, 6)$. Người $0$ và $1$ lấp đầy chuyến $1$; người $2$ bắt đầu chuyến $2$ với $6$ chỗ trống.

Đường tốt nhất đến mask $0011 = (1,0)$, thêm người $3$ (nặng $7$). $7 > 0$, mở chuyến mới. $dp[1011] = (2, 8-7) = (2, 1)$. Cũng từ mask $0101=(1,3)$+người $3$: $7>3$, cho $(2,1)$. Và từ mask $1001=(2,1)$+người $1$: $5>1$, cho $(3,3)$. Tốt nhất: $(2,1)$. Tất cả các đường đều đồng ý $2$ chuyến.

Từ mask $0110 = (1,1)$, thêm người $3$ (nặng $7$). $7 > 1$, mở chuyến mới. $dp[1110] = (2, 8-7) = (2, 1)$. Từ mask $1100=(2,6)$+người $1$: $5 \leq 6$, vừa! Ứng viên $(2,1)$. Và từ mask $1010=(2,1)$+người $2$: $2>1$, cho $(3,6)$. Tốt nhất: $(2, 1)$. Tất cả cho $2$ chuyến.

$dp[1101]$ = mask chứa người $\{0,2,3\}$. Đường tốt nhất: từ mask $0101=(1,3)$+người $3$: $7>3$, cho $(2,1)$. Từ mask $1100=(2,6)$+người $0$: $3 \leq 6$, cho $(2,3)$. Đường thứ hai tốt hơn – cùng $2$ chuyến nhưng còn trống $3$ thay vì $1$. $dp[1101] = (2, 3)$.

Cuối cùng, $dp[1111]$ – cả $4$ người. Ta kiểm tra chuyển trạng thái từ tất cả mask thiếu đúng một người. Từ $dp[0111]=(2,6)$+người $3$ ($w=7$): $7>6$, chuyến mới, ứng viên $(3,1)$. Từ $dp[1011]=(2,1)$+người $2$ ($w=2$): $2>1$, chuyến mới, ứng viên $(3,6)$. Từ $dp[1101]=(2,3)$+người $1$ ($w=5$): $5>3$, chuyến mới, ứng viên $(3,3)$. Từ $dp[1110]=(2,1)$+người $0$ ($w=3$): $3>1$, chuyến mới, ứng viên $(3,3)$.

Cả bốn chuyển trạng thái đều cho $3$ chuyến. Sức chứa còn lại tốt nhất là $6$ (từ $dp[1011]$+người $2$). $dp[1111] = (3, 6)$. Nhưng đáp án chỉ là số chuyến: $3$.

Đáp án: $dp[1111].\text{số\_chuyến} = 3$. Số chuyến thang máy tối thiểu cho cân nặng $[3, 5, 2, 7]$ với sức chứa $8$ là $3$. Một cách phân nhóm tối ưu: chuyến $1$ = $\{$người $1$, người 0CELL0\} ($2$), chuyến $3$ = $\{$người $3$$\}$ ($7$). QHĐ bitmask đã duyệt tất cả $2^4 = 16$ tập con trong thời gian $O(2^n \cdot n)$.