Cần giúp bài dùng thuật toán tham lam để tính tổng đường đi nhỏ nhất trên mảng 2 chiều

[q1212q11111 (Bùi Minh Tiên)]

Dề bài về thuật toán tham lam.

[Mai_Huu (Mai Hữu)]

thuật toán thế này nhé:
đầu tiên từ vị trí ban đầu. bạn xét 3 vị trí là phải, dưới và chéo. xem giá trị của cái nào là bé nhất thì đi tới vị trí số bé nhất đó. sau đó từ vị trí vừa tìm dc lại xét lại như trên. TH mà đã đi tới cuối ở 2 bên thì chỉ đi về 1 hướng thôi

[minhthai (mt)]

Bạn đã làm thử theo hướng nào rồi?

[q1212q11111 (Bùi Minh Tiên)]

em có 2 bài code tưởng tự vậy.
1 cái là đi từ trái qua phải. và 1 cái đi từ trên xuống dưới. củng kiểm tra 3 ô.

cái code này là đi từ trái qua pải 1 hướng em làm dc

int thamlam(int a[][MAX], int n, int path[]) {
	int max, tong;
	max = a[0][0];
	int vtdau;
	int vt;
	for (int i = 1; i < n; i++)
	{
		int j = 0;
		if (a[i][j] >= max)
		{
			max = a[i][j];
			vtdau = i;
		}
	}
	path[0] = vtdau;
	tong = max;
	int dem = 1;
	int i = vtdau;
	for (int j = 0; j < n - 1; j++)
	{
		max = sosanh(a[i + 1][j + 1], a[i][j + 1], a[i - 1][j + 1]);
		if (a[i + 1][j + 1] == max) vt = i + 1;
		if (a[i][j + 1] == max) vt = i;
		if (a[i - 1][j + 1] == max) vt = i - 1;
		path[dem] = vt;
		dem++;
		tong += max;
		i = vt;
	}
	return tong;
}

còn cái code này là đi trừ trên xuống dưới

void thamlam(int b[][20], int d, int path1[])
{
	int col;
	path1[0] = b[0][(d * 2 - 1) / 2];
	col = (d * 2 - 1) / 2;
	int max = col - 1;
	for (int i = 1; i<d; i++) {
		for (int j = -1; j <= 1; j++)
		{
			if (b[i][col + j] > b[i][max] && col + j >= 0 && col + j<(d * 2 - 1))
			{
				max = col + j;
			}
		}
		path1[i] = b[i][max];
		col = max;
	}
}

Nhưng em ko piết kết hợp sao để làm ra cài bài kia cả.

[chichi]

Ý tưởng tạo thêm dòng N và cột N, đặt gía trị trên cột và dòng này bằng MAX_INT -> í là lúc xét khi đến biên N-1 thì không bị đi ra ngoài vì gía trị này luôn lớn hơn ô trong bảng thật, từ vị trí ô (i,j) => xét 3 vị trí (i,j+1),(i+1,j),(i+1,j+1) thằng nào nhỏ thất thì đến, khi đến ô (N-1,N-1) thì thôi

[AI_Android]

Bài này cần gì tham lam nhỉ bạn có thể làm bằng cách Dijkstra +priority_queue độ phức tạp chỉ là ở(n^2)
F[i][j] là đường đi min đến ô i,j
Bắt đầu bằng ô 0,0 push vào queue , mỗi bước lấy phần tử top của queue ( có giá trị f[i][j] min) để update các ô (i+1,j) (j+1,i) và (i+1,j+1) rồi push các ô này vào queue.

[Gio (Gió)]

A_ij là giá trị ở ô ij
F_ij là kết quả tốt nhất tới ô ij
Do từ ô khác tới ô ij chỉ có 3 ô (i-1,j-1) , (i,j-1), (i-1,j) nên kết quả tốt nhất ở ô ij là
F_ij=min(F_i,j-1,F_i-1,j-1,F_i-1,j)+A_ij
Từ đó ta có công thức QHD của bài toán