Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

SPOJ.COM – Thuật toán bài RENT – Rent your airplane and make money

Đề bài:

“ABEAS Corp.” là một công ty rất nhỏ sở hữu duy nhất một chiếc máy bay. Khách hàng của “ABEAS Corp.” là những công ty lớn – những công ty đã thuê để điều tiết khi lượng hàng hóa quá tải. Khách hàng gửi những đơn hàng bao gồm thời gian và giá mà khách hàng sẵn sàng trả cho việc thuê máy bay trong thời gian đó. Tất cả những đơn hàng đã được biết trước. Dĩ nhiên không phải tất cả các đơn hàng đều được chấp nhận, và một vài cái sẽ bị từ chối. Eugene LAWLER, “ABEAS Corp.” muốn đạt được lợi nhuận cao nhất.

Bạn được yêu cầu tính toán giải pháp tối ưu này.

Một ví dụ nhỏ:

Xem xét một trường hợp đó là có 4 đơn hàng như sau:

+ Đơn hàng 1: (Thời gian bắt đầu 0, thời gian sử dụng 5, giá 10)

+ Đơn hàng 2: (Thời gian bắt đầu 3, thời gian sử dụng 7, giá 8)

+ Đơn hàng 3: (Thời gian bắt đầu 5, thời gian sử dụng 9, giá 7)

+ Đơn hàng 4: (Thời gian bắt đầu 6, thời gian sử dụng 9, giá 8)

* Giải pháp tối ưu là bỏ đi đơn hàng 2 và 3, khi đó lợi nhuận sẽ là 10 + 8 = 18. Chú ý rằng, giải pháp chọn lựa đơn hàng 1 và 3 cũng thỏa mãn về mặt thời gian. Tuy nhiên, lợi nhuận chỉ là 10 + 7 = 17.

Đầu vào:

Dòng đầu tiên là số T, số lượng test case, T <= 30. Dòng đầu của mỗi test case là số n, n <= 10000. Tiếp theo là n dòng, mỗi dòng là một đơn hàng, bao gồm 3 số nguyên, lần lượt là thời gian bắt đầu (st), thời gian sử dụng (d) và giá (p), với điều kiện là 0 <= st, d <= 1000000 và 0 <= p < 100000.

Đầu ra:

Với mỗi test case, in ra số cần tìm.

Ví dụ:

Đầu vào:

1
4
0 5 10
3 7 14
5 9 7
6 9 8
Đầu ra:
18

Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/RENT/

Phân tích:

+ Ở đây tôi sử dụng kết hợp thuật toán tham lam Greedy, thuật toán chia để trị Divide and conquer và thuật toán quy hoạch động Dynamic programming.

+ Trong đó, thuật toán tham lam thể hiện ở chỗ đó là đầu tiên tôi sẽ sử dụng thuật toán sắp xếp nhanh quick sort để sắp xếp các đơn hàng theo thời gian kết thúc tăng dần.

+ Tiếp theo, thuật toán quy hoạch động thể hiện ở chỗ đó là tôi dùng một mảng, trong đó Memo[i] để lưu lại số tiến lớn nhất thu được khi chỉ chọn các đơn hàng từ 1 đến i. Như vậy rõ ràng kết quả cần tìm là Memo[N].

+ Trường hợp cơ sở ở đây là Memo[i] = Price[i] – tức là chỉ chọn 1 đơn hàng thứ i.

+ Ta có công thức quy hoạch động là Memo[i] = Max{Memo[i], Memo[i – 1], Price[i] + Memo[k]}

+ Trong đó: Memo[i – 1] ứng với trường hợp không chọn đơn hàng thứ i; Price[i] + Memo[k] ứng với trường hợp chọn đơn hàng thứ i, và k là số lớn nhất thỏa mãn thời gian kết thúc tại k < thời gian bắt đầu tại i – đảm bảo thời gian không bị chồng lên nhau.

+ Để tìm ra số k nhanh nhất tôi sử dụng thuật toán chia để trị hay tìm kiếm nhị phân.

Lời giải:

(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)

Code C/C++:

#include <iostream>
using namespace std;

const int MAX = 10005;

int N;
int Start[MAX], Finish[MAX], Price[MAX];
long long Memo[MAX];    
// Memo[i] là số tiền lớn nhất khi chỉ chọn các đơn hàng từ 1 đến i

void QuickSort(int left, int right)
{
    int l = left, r = right;
    int pivot = Finish[(l + r) / 2];

    while(l <= r)
    {
        while(Finish[l] < pivot) l++;
        while(Finish[r] > pivot) r--;

        if(l <= r)
        {
            int temp1 = Finish[l];    int temp2 = Start[l];    int temp3 = Price[l];
            Finish[l] = Finish[r];    Start[l] = Start[r];    Price[l] = Price[r];
            Finish[r] = temp1;        Start[r] = temp2;        Price[r] = temp3;    
            l++;
            r--;
        }    
    }

    if(l < right) QuickSort(l, right);
    if(left < r) QuickSort(left, r);
}

// Tìm số k lớn nhất thoả mãn Finish[k] < Start[i]
// Nếu không tìm thấy thì trả về -1
int BinarySearch(int i)
{
    int left = 1, right = i;
    int k;

    while(left < right - 1)
    {
        k = (left + right) / 2;

        if(Finish[k] < Start[i]) left = k;
        else right = k - 1;
    }

    if(Finish[right] < Start[i]) return right;
    if(Finish[left] < Start[i]) return left;
    return -1;
}

int main(int argc, char** argv)
{
    int T, test_case;
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);

    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {
        // Nhập đầu vào
        int d;
        cin >> N;
        for(int i = 1; i <= N; i++)
        {
            cin >> Start[i] >> d >> Price[i];
            Finish[i] = Start[i] + d;
        }

        // Sắp xếp các đơn hàng theo chiều tăng của thời gian kết thúc
        QuickSort(1, N);

        // Trường hợp cơ sở
        for(int i = 1; i <= N; i++)
            Memo[i] = (long long)Price[i];

        for(int i = 2; i <= N; i++)
        {
            // Không chọn đơn hàng thứ i
            if(Memo[i-1] > Memo[i]) Memo[i] = Memo[i-1];

            // Chọn đơn hàng thứ i
            // Tìm số k lớn nhất sao cho Finish[k] < Start[i]
            int k = BinarySearch(i);
            long long temp = (long long)Price[i] + (long long)Memo[k];
            if(k > -1 && temp > Memo[i]) Memo[i] = temp;
        }

        // Print the answer to standard output(screen).
        cout << Memo[N] << endl;
    }
    return 0;//Your program should return 0 on normal termination.
}

Code by Phạm Văn Lâm.

257 views

2 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài RENT – Rent your airplane and make money trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

  2. Van Ba

    Dường như sắp xếp theo chiều tăng dần of time kết thúc như of a chưa tối ưu.
    trong 2 case sau. có vẻ như trả về kết quả chưa là cao nhất. hoặc do e hiểu sai mục đích đề bài. Mong a giải thích giúp e. Cảm ơn a!
    4
    0 9 18
    3 7 14
    5 9 7
    6 9 8
    4
    0 9 18
    3 5 14
    5 9 7
    6 9 8

Để lại bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *