SPOJ.COM - Thuật toán bài HOUSES - Những ngôi nhà

Đề bài:

Một công ty đầu tư xây dựng một khu nhà gồm L căn nhà nằm cạnh nhau trên một con đường. Có N người muốn mua nhà ở khu nhà này, biết rằng người thứ i muốn mua a_i căn nhà và mỗi người đều muốn mua những căn nhà nằm cạnh nhau. Do số căn nhà cần mua có thể nhỏ hơn tổng số căn nhà (L) nên sẽ có một số căn nhà chưa được bán. Để đảm bảo mỹ quan của khu nhà, công ty sẽ luôn luôn bán căn nhà đầu tiên (theo thứ tự từ trái sang phải).

Biết yêu cầu của những người mua, một cách bán những căn nhà của công ty có thể được biểu diễn bằng 1 dãy gồm L số. Trong đó số thứ i bằng 0 nếu căn nhà thứ i chưa được bán và bằng k nếu căn nhà thứ i được bán cho người thứ k.

Ví dụ: khi L=4, N=2, a₁ = 2, a₂=1, dãy "2 0 1 1" thể hiện một cách bán những căn nhà của công ty: căn nhà đầu tiên bán cho người thứ 2, căn nhà thứ 3 và thứ 4 bán cho người đầu tiên và căn nhà thứ 2 được để lại.

Yêu cầu: Hãy giúp công ty liệt kê các cách bán những căn nhà. Các cách bán căn nhà được liệt kê theo thứ tự từ điển của dãy số biểu diễn. Nếu số cách bán căn nhà lớn hơn 1000, chỉ cần liệt kê 1000 cách đầu tiên. (Biết rằng dãy a có thứ tự từ điển đứng trước dãy b nếu và chỉ nếu tồn tại chỉ số j, sao cho a_i = b_i với mọi i < j và a_j < b_j).

Đầu vào

• Dòng đầu tiên: chứa 2 số nguyên L, N.
• Dòng thứ 2 chứa N số nguyên, tương ứng là các giá trị a₁, a₂, …, a_n.

Giới hạn

• 1 ≤ L ≤ 100.
• 1 ≤ N ≤ 20.
• a₁ + a₂ + ... + a_N ≤ L.

Đầu ra

Gồm nhiều dòng, mỗi dòng tương ứng với dãy số biểu diễn một cách bán những căn nhà của công ty, 2 số liên tiếp của dãy số được cách nhau bởi một khoảng trắng. Các dãy số được liệt kê theo thứ tự từ điển.

Ví dụ

Đầu vào:

4 2 
2 1 

Đầu ra:

1 1 0 2 
1 1 2 0 
2 0 1 1 
2 1 1 0 

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

Phân tích

Trong bài toán này mình sẽ sử dụng thuật toán quay lui có điều kiện - backtracking. Tư tưởng là lần lượt xét từng căn nhà. Tại mỗi căn nhà, mình sẽ xét 2 khả năng có thể là nó được bán hoặc không được bán.

Trong trường hợp căn nhà được bán, mình lại lần lượt xét các trường hợp là nó được bán cho người thứ 1, 2, 3,..., i,..N. Và bạn cần nhớ rằng, mỗi khi nhà được bán cho người thứ i thì đồng nghĩa với a_i căn nhà sẽ được bán cho người thứ i.

Trong trường hợp căn nhà không được bán, điều này chỉ xảy ra khi số căn nhà còn lại đủ cho những người còn lại. Vì bắt buộc phải bán nhà cho N người.

Sau đây là lời giải bài toán sử dụng thuật toán quay lui có điều kiện - backtracking.

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 = 105;

int N;                  // Số người muốn mua nhà
int L;                  // Số lượng ngôi nhà
int a[MAX];             // Biểu diễn rằng : người thứ i sẽ mua a[i] ngôi nhà
int r[MAX];             // Mảng lưu kết quả
int SoldHouses;         // Tổng số ngôi nhà được mua
int FreeHouses;         // Tổng số ngôi nhà sẽ không được mua
int NumAnswer;          // Đếm số kết quả
bool Visit[MAX];        // Đánh dấu xem người thứ i đã mua hay chưa

/*
* idHouse: id ngôi nhà đang xét
* IgnoreHouses: tổng số những ngôi nhà đã bị bỏ qua, không bán
*/
void Check(int idHouse, int IgnoreHouses)
{
	// Nếu đã đủ 1000 kết quả thì return
	if(NumAnswer == 1000) return;

	// Nếu duyệt đến cuối cùng mà số nhà đã được bán hết thì ta được 1 kết quả
	if(idHouse >= L + 1)
	{
		NumAnswer++;
		for(int i = 1; i <= L; i++)
			cout << r[i] << " ";
		cout << endl;
		return;
	}

	// Không bán
	if(idHouse > 1 && IgnoreHouses < FreeHouses) Check(idHouse + 1, IgnoreHouses + 1);

	// Bán
	// Lần lượt bán cho người thứ i đến người thứ n
	for(int i = 1; i <= N; i++)
		if(!Visit[i])
		{
			Visit[i] = true;
			for(int j = 0; j < a[i]; j++)
				r[idHouse + j] = i;

			Check(idHouse + a[i], IgnoreHouses);

			for(int j = 0; j < a[i]; j++)
				r[idHouse + j] = 0;
			Visit[i] = false;
		}
}

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

	// Nhập đầu vào
	cin >> L >> N;

	SoldHouses = 0;
	for(int i = 1; i <= N; i++)
	{
		cin >> a[i];
		SoldHouses += a[i];
		Visit[i] = false;
	}

	FreeHouses = L - SoldHouses;
	NumAnswer = 0;

	// Xét các trường hợp
	Check(1, 0);

	return 0;
}