Bài toán Tổ chức tham quan (Đề thi Tin học trẻ)

Bài toán

Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức hội thi Tin học trẻ tổ chức cho N đoàn ( đánh từ số 1 đến N) mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách Khách sạn Hoàng Đế di km (i=1,2,…., N). Hội thi có M xe taxi đánh số từ 1 đến M (M³N) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km.

Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.

Dữ liệu: File văn bản P2.INP:

– Dòng đầu tiên chứa hai số nguyên dương N, M (N£M£200);

– Dòng thứ hai chứa các số nguyên dương d₁, d₂, …, dN;

– Dòng thứ ba chứa các số nguyên dương v₁, v₂, …, vM.

– Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng.

Kết quả: Ghi ra file văn bản P2.OUT:

– Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);

– Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, …, N).

Ví dụ:

Cài đặt bài toán với Python

Để giải quyết bài toán này, ta có thể sử dụng giải thuật Greedy. Theo đó, ta sắp xếp các xe taxi theo thứ tự tăng dần của mức tiêu thụ xăng. Sau đó, ta liên tiếp gán các xe cho các đoàn đi thăm quan, bắt đầu từ xe có mức tiêu thụ xăng thấp nhất cho đến khi gán hết các đoàn.

Để giải quyết bài toán trên bằng thuật toán Greedy, ta có thể thực hiện các bước sau:

1. Đọc dữ liệu từ file và lưu vào các biến tương ứng.
2. Sắp xếp các xe taxi theo thứ tự tăng dần của mức tiêu thụ xăng.
3. Với mỗi đoàn thăm quan, tìm xe taxi có mức tiêu thụ xăng thấp nhất mà vẫn đủ khả năng chở được đoàn đó.
4. Lưu kết quả và ghi vào file output.

# Đọc dữ liệu từ file
with open("P2.INP", "r") as f:
    # Đọc N, M
    N, M = map(int, f.readline().split())
    # Đọc d1, d2, ..., dN
    d = list(map(int, f.readline().split()))
    # Đọc v1, v2, ..., vM
    v = list(map(int, f.readline().split()))

# Sắp xếp các xe taxi theo thứ tự tăng dần của mức tiêu thụ xăng
taxis = [(i, v[i-1]) for i in range(1, M+1)]
taxis.sort(key=lambda x: x[1])

# Khởi tạo biến lưu lượng xăng dầu cần dùng
total_gas = 0

# Khởi tạo biến lưu chỉ số xe taxi phục vụ đoàn i
taxi_for_group = [0] * N

# Duyệt qua từng đoàn thăm quan
for i in range(N):
    # Tìm xe taxi có mức tiêu thụ xăng thấp nhất mà vẫn đủ khả năng chở được đoàn đó
    for j in range(M):
        if d[i] <= taxis[j][1]:
            taxi_for_group[i] = taxis[j][0]
            total_gas += d[i] * taxis[j][1]
            break

# Ghi kết quả vào file
with open("P2.OUT", "w") as f:
    f.write(str(total_gas) + "\n")
    for i in taxi_for_group:
        f.write(str(i) + "\n")

Cài đặt bài toán với C++

#include <bits/stdc++.h>
using namespace std;

int n, m, d[205], v[205], ans[205];
bool used[205];

int main() {
    freopen("P2.INP", "r", stdin);
    freopen("P2.OUT", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> v[i];
    }

    // Sắp xếp các xe taxi theo thứ tự tăng dần của mức tiêu thụ xăng
    vector<pair<int, int>> taxi;
    for (int i = 1; i <= m; i++) {
        taxi.push_back({v[i], i});
    }
    sort(taxi.begin(), taxi.end());

    // Liên tiếp gán các xe cho các đoàn đi thăm quan
    int cost = 0;
    for (int i = 1; i <= n; i++) {
        for (auto t : taxi) {
            if (!used[t.second]) {
                ans[i] = t.second;
                used[t.second] = true;
                cost += d[i] * t.first;
                break;
            }
        }
    }

    cout << cost << endl;
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}

Đánh giá độ phức tạp

Trong thuật toán Greedy được sử dụng để giải quyết bài toán này, ta sẽ sắp xếp các xe taxi theo thứ tự tăng dần của mức tiêu thụ xăng, sau đó chọn lần lượt các xe taxi có mức tiêu thụ xăng nhỏ nhất để phục vụ cho các đoàn đi thăm quan.

Với phương pháp này, ta không cần phải tính toán tất cả các trường hợp có thể xảy ra, mà chỉ cần chọn ra giải pháp tốt nhất tại từng bước. Tuy nhiên, việc chọn ra giải pháp tốt nhất tại từng bước không đảm bảo cho việc chọn ra giải pháp tốt nhất cho toàn bộ bài toán.

Vì vậy, độ phức tạp của thuật toán Greedy được sử dụng để giải bài toán này là O(nlogn), trong đó n là số lượng xe taxi.

Lưu ý:

Bài toán này có thể giải bằng nhiều thuật toán khác nhau, trong đó có một số thuật toán nổi bật như:

1. Thuật toán quy hoạch động (Dynamic Programming): Cách tiếp cận này tập trung vào việc tính toán và lưu trữ tất cả các giá trị con phù hợp trong một bảng truy cập nhanh để sử dụng lại. Tuy nhiên, độ phức tạp của thuật toán quy hoạch động thường cao hơn so với các thuật toán Greedy.

2. Thuật toán tìm kiếm địa phương (Local Search): Cách tiếp cận này bắt đầu từ một giải pháp khởi tạo và cố gắng tìm kiếm các giải pháp tốt hơn bằng cách thực hiện các thay đổi địa phương. Ví dụ, thay đổi xe taxi phục vụ đoàn khách hoặc thay đổi địa điểm thăm quan của đoàn khách.

3. Thuật toán tìm kiếm theo đám mây (Swarm Intelligence): Cách tiếp cận này sử dụng phương pháp tìm kiếm đồng thời của một đám mây các giải pháp để tìm kiếm các giải pháp tối ưu. Ví dụ, thuật toán ACO (Ant Colony Optimization) sử dụng mô phỏng quá trình tìm kiếm thức ăn của kiến để giải quyết bài toán đi du lịch.

4. Thuật toán tham lam ngẫu nhiên (Randomized Greedy): Cách tiếp cận này kết hợp giữa phương pháp tham lam và sử dụng ngẫu nhiên để tránh bị mắc kẹt ở các giải pháp cục bộ. Ví dụ, thuật toán GRASP (Greedy Randomized Adaptive Search Procedure) sử dụng một phương pháp tham lam để tạo ra một giải pháp khởi tạo, sau đó sử dụng phương pháp tham lam ngẫu nhiên để tìm kiếm các giải pháp tốt hơn.

5. Thuật toán di truyền (Genetic Algorithm): Cách tiếp cận này mô phỏng quá trình tiến hóa của các cá thể để tìm kiếm các giải pháp tối ưu. Ví dụ, thuật toán GA (Genetic Algorithm) sử dụng các toán tử di truyền như lai ghép, đột biến, chọn lọc để tìm kiếm các giải pháp tốt hơn.

Các bạn thử cài đặt bài toán này với các thuật toán đã nêu ở trên nhé. Chúc các bạn thành công!