SPOJ.COM - Thuật toán bài PIZZALOC - Pizza Location

Posted on October 17th, 2016

Đề bài:

Picko muốn mở một số cửa hàng pizza tại 1 số địa điểm. Bánh pizza sẽ cung cấp cho mọi khách hàng nằm trong hình tròn bán kính R với tâm là các địa điểm được chọn.

Xác định số khách hàng lớn nhất có thể phục vụ.

Input

Dòng đầu là hai số K, R : số nhà hàng có thể được mở và bán kính phục vụ của mỗi nhà hàng,1 ≤ K ≤ 10, 1 ≤ R ≤ 500.

Dòng thứ hai là M, số địa điểm có thể đặt nhà hàng, K ≤ M ≤ 20.

M dòng tiếp theo, mỗi dòng là 2 số nguyên X và Y, -1000 ≤ X,Y ≤ 1000.

Dòng tiếp theo là N, số khu nhà, 1 ≤ N ≤ 100.

Mỗi dòng trong N dòng tiếp theo là 3 số nguyên X, Y , S, là tọa độ và số người ở khu nhà đó, -1000 ≤ X,Y ≤ 1000, 1 ≤ S ≤ 100.

Khu nhà nằm trong bán kính của nhà hàng nếu khoảng cách giữa chúng <= R. Không có 2 khu nhà tại cùng 1 địa điểm.

Output

Ghi ra số người tối đa có thể được phục vụ.

Ví dụ

pizza.in

2 2 
3
1 0
4 0 
7 0 
4 
0 0 1
3 0 7
5 0 9 
8 0 1 

pizza.out

18 

pizza.in

2 2 
3 
-2 0 
0 1 
3 0 
8 
-3 1 1 
-3 0 1 
-3 -1 1 
-2 -1 1 
0 0 3 
0 2 1 
2 1 3 
4 0 2 

pizza.out

12 

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

Phân tích

Trong bài toán này, ta sẽ phải xây K nhà hàng trong M vị trí. Ở đây, thực chất là ta sẽ phải liệt kê ra tổ hợp chập K của M phần tử trường hợp.

Với mỗi trường hợp, ta sẽ kiểm tra xem mỗi ngôi nhà có được phục vụ bởi nhà hàng nào hay không.

Mình sẽ triển khai bài toán sử dụng thuật toán quay lui có điều kiện - Backtracking.

Một điều chú ý là: với mỗi vị trí có thể đặt nhà hàng, mình sẽ kiểm tra xem tại vị trí đó, nếu như mình đặt nhà hàng thì nó sẽ phục vụ được cho những ngôi nhà nào. Kết quả mình sẽ lưu được vào một mảng. Điều này sẽ tránh bị time limit.

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_PLACE = 21;
const int MAX_HOUSE = 101;

int NumRest, R;                             // Số lượng nhà hàng và bán kính
int NumPlac;                                // Số địa điểm có thể đặt nhà hàng
int XPlace[MAX_PLACE], YPlace[MAX_PLACE];   // Toạ độ các điểm có thể đặt nhà hàng

int NumHous;                                // Số khu nhà
int XHouse[MAX_HOUSE], YHouse[MAX_HOUSE];   // Toạ độ các khu nhà

int NumPeop[MAX_HOUSE];                     // Số người ở mỗi khu nhà
int MaxPeop;                                // Số người tối đa có thể phục vụ
int SumPeop;                                // Tổng số người

// Lưu lại vị trí đã đặt của các nhà hàng
int PRest[MAX_PLACE];                       

// Kiểm tra xem một vị trí có thể phục vụ những ngôi nhà nào
int Reach[MAX_PLACE][MAX_HOUSE];    

// Đếm số nhà mà nhà hàng có thể phục vụ ứng với mỗi vị trí
int Count[MAX_PLACE];               

/*
* @PARAM: pos : lưu vị trí đang xét
* @PARAM: numIgnore : số vị trí ko đặt
* @PARAM: numRestor : số nhà hàng đã đặt
*/
void Check(int pos, int numIgnore, int numRestor)
{
	if(pos == NumPlac)
	{
		// Kiểm tra với những cách đã đặt cách nào phục vụ nhiều người nhất
		// Duyệt lần lượt các ngôi nhà, xem với mỗi ngôi nhà nó có được phục vụ không
		
		// Những người được phục vụ
		int SerPeop = 0;		
		int Mark[MAX_HOUSE] = {0};

		for(int j = 0; j < NumRest; j++)
		{
			int idRest = PRest[j];

			for(int i = 0; i < Count[idRest]; i++)
			{
				// Chú ý: mỗi ngôi nhà chỉ được tính một lần.
				int idHouse = Reach[idRest][i];
				if(Mark[idHouse] == 0)
				{
					SerPeop += NumPeop[idHouse];
					Mark[idHouse] = 1;
				}

				// Nếu đã phục vụ được tối đa rồi thì thoát luôn
				if(SerPeop == SumPeop) break;
			}
		}
			
		if(SerPeop > MaxPeop) MaxPeop = SerPeop;

		return;
	}

	if(MaxPeop == SumPeop) return;
	
	// Đặt nhà hàng
	if(numRestor < NumRest)
	{
		PRest[numRestor] = pos;
		Check(pos + 1, numIgnore, numRestor + 1);
		if(MaxPeop == SumPeop) return;
	}

	// Ko đặt nhà hàng
	if(numIgnore < NumPlac - NumRest)
		Check(pos + 1, numIgnore + 1, numRestor);
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("input.txt","r",stdin);

	cin >> NumRest >> R >> NumPlac;
	for(int i = 0; i < NumPlac; i++)
		cin >> XPlace[i] >> YPlace[i];

	SumPeop = MaxPeop = 0;

	cin >> NumHous;
	for(int i = 0; i < NumHous; i++)
	{
		cin >> XHouse[i] >> YHouse[i] >> NumPeop[i];
		SumPeop += NumPeop[i];
		Count[i] = 0;
	}

	// Lưu lại những ngôi nhà mà tại mỗi vị trí, nhà hàng có thể phục vụ
	for(int j = 0; j < NumPlac; j++)
		for(int i = 0; i < NumHous; i++)
		{
			int temp = (XHouse[i] - XPlace[j])*(XHouse[i] - XPlace[j]) + 
				(YHouse[i] - YPlace[j])*(YHouse[i] - YPlace[j]);

			if(temp <= R*R) Reach[j][Count[j]++] = i;
		}

	// Đặt NumRest nhà hàng trong NumPlac vị trí
	Check(0, 0, 0);

	cout << MaxPeop << endl;

	return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!