博客文章

有些单元格不可达的硬币收集问题

作者: andy.      时间: 2016-04-29 20:49:10

这个属于动态规划问题中的一个入门问题。简单描述一下问题,机器人从左上方需要收集尽可能多的硬币带到右下方的单元格。























设Cij表示第i行,第j列单元格的硬币数量,F(i,j)为机器人截止第i行第j列能够收集的最大硬币数。于是可以得到:

1、 第一行F(1,j)由F(1, j-1)决定。(j>1)

2、第一列F(i,1) 由F(i-1,1)决定。(i>1)

3、当i,j>1时,F(i,j) = max{ F(1, j-1), F(i-1,1)}+ Cij.

算法的实现也比较简单:

RCC(C[1..n, 1..m])
       F[1, 1] = C[1, 1];
       for j = 2 to m    //第一行 收集的最大硬币数
              F[1, j] = F[1, j - 1] + C[1, j]
             
       for i = 2 to n{
              F[i, 1] = F[i - 1, 1] + C[i, j]    //第一列 收集的最大硬币数
              for i = 2 to m
                     F[i, j] = MAX(F[i - 1, j], F[i, j - 1]) + C[i, j]
       }
       return F[n, m]

该情况讨论到此。重点在有些单元格不可达,如下图的状况:


X






X




X






X

X

X



 

可以直接观察得到如果单元格不可达的情况分为两种:

1、该单元格的左、上单元格均不达。

2、该单元格本身不可达。

于是在上述的的算法计算F[i,j]前先判断是否不可达,这儿就不给出算法的描述了。直接给出代码,注意修改部分。全部代码:

#include <stdio.h>
#include <stdlib.h>
#define MAX(x,y)(x>y?x:y)

void printMap(int(*map)[6]) {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 6; j++)
			printf("%3d", map[i][j]);
		printf("\n");
	}
}

int main() {
	int map[5][6] = {
		{ 0, -1, 0, 1, 0, 0 },
		{ 1, 0, 0, -1, 1, 0 },
		{ 0, 1, 0, -1, 1, 0 },
		{ 0, 0, 0, 1, 0, 1 },
		{ -1, -1, -1, 0, 1, 0 }
	};
	printf("before:\n");
	printMap(map);
	for (int i = 1; i < 6; i++)
		if (map[0][i - 1] == -1 || map[0][i] == -1)//单元格是否不可达
			map[0][i] = -1;
		else
			map[0][i] = map[0][i - 1] + map[0][i];

	for (int i = 1; i < 5; i++) {
		if (map[i - 1][0] == -1 || map[i][0] == -1)//单元格是否不可达
			map[i][0] = -1;
		else
			map[i][0] = map[i - 1][0] + map[i][0];

		for (int j = 1; j < 6; j++)
			if ((map[i - 1][j] == -1 && map[i][j - 1] == -1) || map[i][j] == -1)
				map[i][j] = -1;
			else
				map[i][j] = MAX(map[i - 1][j], map[i][j - 1]) + map[i][j];
	}
	printf("after:\n");
	printMap(map);
}

        最后给出运行结果:

before:
  0 -1  0  1  0  0
  1  0  0 -1  1  0
  0  1  0 -1  1  0
  0  0  0  1  0  1
 -1 -1 -1  0  1  0
after:
  0 -1 -1 -1 -1 -1
  1  1  1 -1 -1 -1
  1  2  2 -1 -1 -1
  1  2  2  3  3  4
 -1 -1 -1  3  4  4