[Lý thuyết giải thuật] Một số bài tập về giải thuật và cách giải
Trả lời cùng với trích dẫnHướng dẫn giải thuật cho Bài 1:
Bài này có thể giải quyết bằng phương pháp quy hoạch động.
Gọi f(i) là số tiền ít nhất phải dùng khi cần đi quãng đường i (km)
Rõ ràng f(0)=0;
f(1)=chiphi(1) (Số tiền để xe đi 1 km)
Với 2<=i<= L Thì
f(i)= MIN(f(i-j)+chiphi(j)) với 1<=j<=b và j<=i
Và f(L) chính là chi phí nhỏ nhất cần dùng khi cần đi đoạn đường độ dài L.
Chắc nhiều bạn còn lạ lẫm với cách giải quy hoạch động, nên mình sẽ giải thích cụ thể hơn như sau.
Thay vì giải quyết bài toán tìm chi phí nhỏ nhất khi cần đi L đoạn đường, ta sẽ giải quyết L bài toán nhỏ hơn: Tìm chi phí nhỏ nhất khi cần đi 1, 2, 3.... L (km)
rồi từ đó phối hợp lại để giải bài toán ban đầu.
Lời giải Các bài toán con trên nhận được từ các lởi giải trước đó theo công thức quy hoạch động ở trên.
Nói theo ngôn ngữ tự nhiên, khi cần tính toán xem chi phí nhỏ nhất khi cần đi i km là bao nhiêu ta sẽ đặt ra các giả thiết, tại lúc trước đó ta đã xuất phát từ đâu, và với vị trí xuất phát đó ta sẽ có được chi phí tương ứng để có mặt ở vị trí hiện tại. Chi phí nhỏ nhất chính là MIN của các giá trị trên.
Khi cài đặt, ta xây dựng một mảng Int f[Maxl] để lưu giữ kết quả các bài toán con
Việc tìm lời giải các bài toán con có thể mô tả như sau:
Lời giản của bài toán khi đó sẽ là F[L]PHP Code:f[0]:= 0;
f[1]:= c[1];
For i:=2 To L Do
Begin
Min:= Maxint;
For j:=1 To b Do
If i>= j Then
If f[i-j] + c[j]< Min Then
Begin
Min:= f[i-j] + c[j];
End;
f[i]:= Min;
End;
End;
