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

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 mình 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 mình 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à mình 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 mình sử dụng thuật toán chia để trị hay tìm kiếm nhị phân.

Lời giải

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 mình 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 mình 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 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.
}