SPOJ.COM - Thuật toán bài CTAIN - Containers

Posted on December 3rd, 2016

Đề bài:

Bạn được đưa cho n thùng chứa, trong đó 1 <= n <= 4. Lúc đầu, tất cả chúng đều đầy nước. Dung lượng tối đa của thùng thứ i là một số tự nhiên oi  thỏa mãn 1 <= oi <= 49.

Có 3 loại hành động có thể thực hiện:

  1. Đổ toàn bộ nước từ một thùng sang một thùng khác
  2. Đổ đầy một thùng với phần nước từ một thùng khác.
  3. Đổ hết nước từ một thùng xuống cống

Nhiệm vụ:

Viết một chương trình cho mỗi test case:

  • Đọc vào số lượng thùng n, dung lượng tối đa của mỗi thùng và lượng nước được yêu cầu từ mỗi thùng.
  • Kiểm tra xem nếu tồn tại một chuỗi hành động có thể dẫn tới lượng nước yêu cầu của mỗi thùng, thì tính xem số bước nhỏ nhất để làm được việc đó.
  • In ra kết quả. Kết quả là số bước nhỏ nhất để đạt được yêu cầu hoặc in ra "NO" nếu không thể đạt được yêu cầu.

Đầu vào

Một số nguyên ở dòng đầu tiên, là số lượng test case, theo sau là một dòng trắng. Cho biết là sẽ không quá 20 test case.

Mỗi test case, dòng đầu tiên sẽ là một số nguyên dương n, với n <= 4 là số lượng thùng. Dòng tiếp theo là n số nguyên dương, là dung lượng tối đa của mỗi thùng oi , thỏa mãn 1 <= oi <= 49. Dòng tiếp theo sẽ là n số nguyên dương wi, là lượng nước yêu cầu của mỗi thùng, thỏa mãn 0 <= wi <= oi. Tất cả số nguyên ở dòng thứ 2 và thứ 3 của mỗi test case được cách nhau bởi một dấu cách. Các test case được phân cách nhau bởi một dấu cách.

Đầu ra

Mỗi test case in ra một số nguyên - là số bước nhỏ nhất để đạt được yêu cầu. Ngược lại thì in ra "NO".

Ví dụ

Đầu vào:

2

3
3 5 5
0 0 4

2
20 25
10 16

Đầu ra:

6
NO

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

Phân tích

  • Tại một thời điểm, ta sẽ có một trạng thái ứng với lượng nước trong mỗi thùng. Bài toán cho trước trạng thái ban đầu và yêu cầu tìm ra số bước nhỏ nhất để đạt được trạng thái đích. Do đó, mình sẽ dụng thuật toán tìm kiếm theo chiều rộng BFS để giải quyết bài toán.

  • Vì có tối đa là 4 thùng nên mình sẽ sử dụng mảng 4 chiều, trong đó mỗi chiều sẽ có tối đa 50 phần tử từ 0 đến 49 đại diện cho lượng nước từ 0 đến 49, để đánh dấu số bước nhỏ nhất có thể đạt được trạng thái đó. Ban đầu các giá trị của mảng sẽ được đánh dấu là MAXINT. Sau quá trình duyệt nếu như giá trị của mảng tại trạng thái cần tìm vẫn là MAXINT thì có nghĩa là sẽ không có cách để đạt được trạng thái đó và in ra là "NO". Ngược lại mình sẽ in ra giá trị của mảng tại trạng thái đó.

  • Tại một trạng thái thì các trạng thái kề với nó sẽ có được bằng cách thực hiện 3 hành động cho trong đề bài.

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 = 5;
const int MAX_QUEUE = 1000000;
const int MAX_INT = 1 << 30;
const int MAX_STATE = 50;

int  N;				//số lượng thùng
int Capacity[MAX];	//dung lượng mối thùng
int Water[MAX];		//lượng nước hiện tại mỗi thùng
int Need[MAX]; 		//lượng nước cần
int Answer;			//kết quả
bool Flag, Finish;

// Đánh dấu trạng thái
int  State[MAX_STATE][MAX_STATE][MAX_STATE][MAX_STATE];

typedef struct Point
{
	int *water;
	int step;
	Point():step(0),water(0){}
	Point(int st, int *wa):step(st),water(wa){}
}Point;

Point queue[MAX_QUEUE];
int fr, re, leng;

/**
* copy mảng: từ mảng src sang mảng dst*/
void CpyArray(int *dst, int *src)
{
	for(int i = 0; i < N; i++)
		dst[i] = src[i];
}

// implement hàng đợi vòng
void Enqueue(Point p)
{
	queue[re] = p;
	re = (re + 1) % MAX_QUEUE;
	leng++;
}

Point Dequeue()
{
	Point p = queue[fr];
	fr = (fr + 1) % MAX_QUEUE;
	leng--;
	return p;
}

/**
* Lấy giá trị của mảng 4 chiều tại một trạng thái
*/
int GetValueState(int *tmp)
{
	int a,b,c,d;
	a = b = c = d = 0;

	if(N == 1) a = tmp[0];
	else if(N == 2) {a = tmp[0]; b = tmp[1];}
	else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];}
	else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];}

	return State[a][b][c][d];
}

/**
* Xét giá trị value cho mảng 4 chiều tại trạng thái cho trước
*/
void SetValueState(int *tmp, int value)
{
	int a,b,c,d;
	a = b = c = d = 0;

	if(N == 1) a = tmp[0];
	else if(N == 2) {a = tmp[0]; b = tmp[1];}
	else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];}
	else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];}

	State[a][b][c][d] = value;
}

// Implement BFS
void BFS(Point st)
{
	fr = re = leng = 0;
	SetValueState(st.water,0);
	Enqueue(st);

	while(leng > 0)
	{
		Point p = Dequeue();
		
		// Duyệt các thùng và thực hiện 3 hành động
		for(int i = 0; i < N; i++)
		{
			// Hành động 1: đổ hết nước đi
			int old_water = p.water[i];
			p.water[i] = 0;

			int *tmp1 = new int[N];
			CpyArray(tmp1, p.water);

			// Kiểm tra xem trạng thái này đã có chưa
			// nếu giá trị tại đó là MAX_INT nghĩa là chưa có
			if(GetValueState(tmp1) == MAX_INT)
			{
				SetValueState(tmp1, p.step + 1);
				Enqueue(Point(p.step + 1, tmp1));
			}
			p.water[i] = old_water;

			// Hành động 2: Đổ đầy bằng 1 thùng khác
			// Hành động này chỉ thực hiện khi thùng chưa đầy
			if(p.water[i] < Capacity[i])
			{
				// thử đổ đầy bằng các thùng còn lại
				for(int j = 0; j < N; j++)
				{
					if(j == i) continue;
					if(Capacity[i] - p.water[i] <= p.water[j])
					{
						int old_water1 = p.water[i], old_water2 = p.water[j];
						p.water[j] = p.water[j] - (Capacity[i] - p.water[i]);
						p.water[i] = Capacity[i];

						int *tmp2 = new int[N];
						CpyArray(tmp2,p.water);

						// Kiểm tra xem trạng thái này đã có chưa
						// nếu giá trị tại đó là MAX_INT nghĩa là chưa có
						if(GetValueState(tmp2) == MAX_INT)
						{
							SetValueState(tmp2,p.step+1);
							Enqueue(Point(p.step+1,tmp2));
						}
						p.water[i] = old_water1;
						p.water[j] = old_water2;
					}
				}
			}

			//Hành động 3: Đổ hết nước sang thùng khác nếu đủ chỗ
			//Xét thử các thùng
			for(int j = 0; j < N; j++)
			{
				if(j == i) continue;
				if(Capacity[j] - p.water[j] >= p.water[i])
				{
					int old_water1 = p.water[i], old_water2 = p.water[j];
					p.water[j] = p.water[j] + p.water[i];
					p.water[i] = 0;

					int *tmp3 = new int[N];
					CpyArray(tmp3,p.water);

					// Kiểm tra xem trạng thái này đã có chưa
					// nếu giá trị tại đó là MAX_INT nghĩa là chưa có
					if(GetValueState(tmp3) == MAX_INT)
					{
						SetValueState(tmp3,p.step+1);
						Enqueue(Point(p.step+1,tmp3));
					}
					p.water[i] = old_water1;
					p.water[j] = old_water2;
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		cin >> N;
		for(int i = 0; i < N; i++)
		{
			cin >> Capacity[i];
			Water[i] = Capacity[i];
		}

		for(int i = 0; i < N; i++)
			cin >> Need[i];

		Answer = MAX_INT;
		for(int i = 0; i < MAX_STATE; i++)
			for(int j = 0; j < MAX_STATE; j++)
				for(int k = 0; k < MAX_STATE; k++)
					for(int m = 0; m < MAX_STATE; m++)
						State[i][j][k][m] = MAX_INT;

		BFS(Point(0, Water));

		Answer = GetValueState(Need);

		if(Answer == MAX_INT) cout << "NO" << endl;
		else cout << Answer << 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!