- Bài toán: Xếp lịch hội thảo
Gợi ý:
- Sắp xếp không giảm theo thời điểm kết thúc.
- Chọn lịch đầu tiên trong danh sách
- Lặp quá trình tìm một cuộc họp tiếp theo có thời điểm bắt đầu không lớn hơn thời điểm kết thúc của cuộc họp trước đó.
- Bài toán: Vận chuyển hàng tối ưu- Lập dãy tỉ số thời gian vận chuyển và cước phạt vận chuyển. ưu tiên thời gian vận chuyển nhanh trước. Nếu cùng thời gian vận chuyển thì ưu tiên tiền phạt; nếu tiền phạt mất nhiều thì vận chuyển trước
-Tạo mảng ghi lại số thứ tự các mặt hàng
- Cách làm bằng cách sắp xếp tăng tỉ số nói trên;
* Chú ý tên[i] =i chính là thứ tự loại hàng cần vận chuyển; nên khi sắp xếp cần phải đổi chỗ cả thứ tự mặt hàng
-Bài toán: Kho sửa tầu
* Lưu ý bài toán cần kiểm tra tính hợp lệ của hoán vị toa tàu ở đường ray ra, dãy các toa ở đường ray vào mặc định là dãy 1, 2, ..., n theo thứ tự từ trái qua phải.
- Gọi (b) = {b1, b2, ..., bn} là dãy toa tàu ở đường ray vào, thì bi = i với i = 1, 2, ..., n.
- Gọi (a) = {a1, a2, ..., an} là dãy các toa tàu ở đường ray ra. Việc kiểm tra tính hợp lệ của dãy (a) như sau:
Lần lượt xét các toa tàu ai ở đường ray ra theo chiều từ trái sang phải, nghĩa là i tăng dần từ 1, 2, ..., đến n.
- Với mỗi toa ai ta tìm xem nó có trong đường ray vào không.
- Nếu ai có trong (b) thì mọi toa tàu d có có chỉ số nhỏ hơn ai chắc chắn đã được đưa vào kho sửa chữa, ví dụ với n = 5, nếu a1 = 4 thì chắc chắn các toa 1, 2, 3 đã được đưa vào kho sửa chữa. Khi đó ta đưa tất cả các toa d này vào kho (tức là đẩy chúng vào một ngăn xếp), trước khi xét toa tầu tiếp theo ở đường ray ra - Nếu ai không có trong (b) thì chắc chắn nó phải ở trong kho, hơn nữa phải ở vị trí cửa kho sửa chữa (đỉnh ngăn xếp). Nếu ai có ở vị trí cửa kho thì ta “lấy nó ra” khỏi kho, nếu ngược lại thì chứng tỏ dãy (a) là dãy hoán vị không hợp lệ tại i, và đây là dấu hiệu duy nhất để kiểm tra một dãy (a) có hợp lệ hay không.
=========
Tất cả các bài cần phải thể hiện thuật toán và cài đặt bằng chương trình cụ thể
