01/10/2018, 12:03
Xin hướng làm bài toán đưa người qua sông
Có N người muốn qua sông vào trời tối, mỗi lần qua chỉ tối đa 2 người qua và cần có đèn để qua, biết khi 2 người qua thì thời gian qua = thời gian người đi chậm nhất và đoàn chỉ có 1 đèn
VD: 4
3 1 4 5 => 14
5
6 8 3 12 1 => 29
10
1 7 10 3 7 3 10 6 5 3 => 55
Bài liên quan
thử cách đấy thì đúng 1 VD thôi
Không tối ưu đâu bạn.
Hi Derfla.
Bạn thử cho người đi chậm nhất và người chậm thứ 2 đi với nhau. Người đi nhánh nhất và nhanh thứ 2 làm nhiệm vụ chuyển dèn về.
N >= 6 thì chọn người đi nhanh sẽ khó hơn.
Hi rogp10.
nếu có 2 người.
thì 2 người đi qua.
Nếu có 3 người (có thời gian đi là 1, 2, 3):
1, 2 đi (2).
1 về (1)
1, 3 đi (3)
=> tổng lại (2) + (1) + (3) = 6.
Nếu có n người (thời gian đi 1, 2, … , n-1, n)
1, 2 đi (2)
1 về (1)
n-1, n đi (n)
2 về (2) (Hoàn thành chuyển hai người đi chậm nhất tốn ít thời gian nhất (2) + (1) + (2) + (n)).
Đệ quy cho n-2 người. đến cuối có 2 trường hợp còn lại 2 người hoặc 3 người.
P/S Không biết cách này có đúng không.
Cho thằng đi nhanh nhất cầm đèn lên thuyền.
Mấy đứa khác bơi theo ánh đèn
Cứ nghĩ là sông toàn cá sấu hoặc cá răng đao
Trở lại vấn đề: một phương án tổng quát hơn là ntn:
Nhưng như vậy vẫn chưa tối ưu, vì người nhanh thứ 4, 5, 6, …, n/2 sẽ phải quay lại. Vậy hai người nhanh nhất sẽ thay phiên làm con thoi.