Một công ty vận tải cần giao hàng đến tất cả các thành phố \(A,\;B,\;C,\;D,\;E\)
18/22
Một công ty vận tải cần giao hàng đến tất cả các thành phố \(A,\;B,\;C,\;D,\;E\) (xem hình vẽ). Chi phí di chuyển giữa các thành phố được mô tả trên hình (tính theo đơn vị nghìn đồng). Xe giao hàng của công ty xuất phát từ thành phố \(A\) đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố \(A\). Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng)?
Liệt kê và so sánh:
Đường đi | Tổng chi phí |
\(A \to B \to C \to E \to D \to A\) | \(900 + 1400 + 1200 + 1400 + 1100 = 6000\) |
\(A \to B \to C \to D \to E \to A\) | \(900 + 1400 + 1300 + 1400 + 1000 = 6000\) |
\(A \to B \to E \to C \to D \to A\) | \(900 + 800 + 1200 + 1300 + 1100 = 5300\) |
\(A \to D \to C \to E \to B \to A\) | \(1100 + 1300 + 1200 + + 800 + 900 = 5300\) |
\(A \to D \to C \to B \to E \to A\) | \(1100 + 1300 + 1400 + 800 + 1000 = 5600\) |
\(A \to D \to E \to C \to B \to A\) | \(1100 + 1400 + 1200 + 1400 + 900 = 6000\) |
\(A \to E \to B \to C \to D \to A\) | \(1000 + 800 + 1400 + 1300 + 1100 = 5600\) |
\(A \to E \to D \to C \to B \to A\) | \(1000 + 1400 + 1300 + 1400 + 900 = 6000\) |
Vậy chi phí thấp nhất của xe giao hàng là \(5300\) nghìn đồng.
Đáp án: 5300.