Xin hướng làm bài toán đưa người qua sông

[Derfla]

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

[Derfla]

thử cách đấy thì đúng 1 VD thôi

[rogp10]

Không tối ưu đâu bạn.

[Phong_Ky_Vo (Tao Không Ngu.)]

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ề.

[rogp10]

N >= 6 thì chọn người đi nhanh sẽ khó hơn.

[Phong_Ky_Vo (Tao Không Ngu.)]

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.

[hungaya (Hung)]

Cho thằng đi nhanh nhất cầm đèn lên thuyền.
Mấy đứa khác bơi theo ánh đèn

[rogp10]

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:

• Cho từng cặp từ nhanh đến chậm chạy qua.
• Bờ bên kia từ nhanh đến chậm chọn 1 người quay lại.
  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.