硬币收集问题

硬币收集问题（动态规划）

问题：

（硬币收集问题）在n*m格木板中放置一些硬币，每一个格子上最多放置一个硬币。在木板的左上方，一个机器人需要收集尽可能多的硬币，并把他们带到右下角的单元格。每一步，机器人可以从当前位置向右或向下移动一格，当遇到一个有硬币的单元格时，就会将该硬币收集起来。设计一个算法，找出机器人能够收集到最大硬币数，并给出路径。

因为这里机器人只能向下和右边 走所以matrix[n,j]的位置确定依赖于 上面和左边

image-20220502205851978

代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
'''
    收集硬币问题：
    （硬币收集问题）在n*m格木板中放置一些硬币，每一个格子上最多放置一个硬币。
    在木板的左上方，一个机器人需要收集尽可能多的硬币，并把他们带到右下角的单元格。
    每一步，机器人可以从当前位置向右或向下移动一格，
    当遇到一个有硬币的单元格时，就会将该硬币收集起来。
    设计一个算法，找出机器人能够收集到最大硬币数，并给出路径。
'''


# 先创建一个地图
map = [
    [1,0,0,0,0],
    [1,1,0,0,0],
    [0,1,1,0,0],
    [0,0,1,0,0],
    [0,0,1,1,1],
    [0,0,0,0,1],

]

# 进行矩阵赋值，这里我们是依靠的上面和左面为基础来生成矩阵
def max_collection(line, column, matrix, rec):

    # 两层for循环来进行矩阵的每一个元素的便利
    for i in range(0,line):
        for m in range(0,column):

            # 如果左边矩阵的最大值大于上面矩阵的最大值，我们就要在rec数组中记录
            # 一下该位置的数据依赖于左边 “L”
            if matrix[i+1][m] > matrix[i][m+1]:
                rec[i][m] = "L"

                # 如果该位置有硬币的话，我们就需要在原来的基础上加1，没有的话就按照原来的就好
                if map[i][m] == 1:
                    matrix[i+1][m+1] = matrix[i+1][m]+1
                else:
                    matrix[i+1][m+1] = matrix[i+1][m]

            # 如果上面边矩阵的最大值大于左边矩阵的最大值，我们就要在rec数组中记录
            # 一下该位置的数据依赖于上边 “U”
            else:
                rec[i][m] = "U"
                if map[i][m] == 1:
                    matrix[i+1][m+1] = matrix[i][m+1]+1
                else:
                    matrix[i+1][m+1] = matrix[i][m+1]

# 追踪数组
# 从整个矩阵的右下角开始来记录每一次的坐标
def track_rec(rec, rec_line, rec_column, route):
    if rec_line == 0 and rec_column == 0:
        route.append((rec_line+1, rec_column+1))
        return 0
    if rec[rec_line][rec_column] == "U":
        route.append((rec_line+1, rec_column+1))
        track_rec(rec, rec_line-1, rec_column, route)
    else:
        route.append((rec_line+1, rec_column+1))
        track_rec(rec, rec_line, rec_column-1, route)

测试数据：

1 0 0 0 0
1 1 0 0 0
0 1 0 0 0
0 1 1 1 0
1 0 0 1 0
1 1 1 1 1

matrix数组为：

0 0 0 0 0 0

0 1 1 1 1 1

0 2 3 3 3 3

0 2 4 4 4 4

0 2 5 6 7 7

0 2 5 6 8 8

0 3 6 7 9 10

rec数组为：

U L L L L

U L L L L

U U L L L

U U L L L

U U U U L

U U U U L

最后追踪效果为

(1, 1) -> (2, 1) ->(2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4) -> (5, 4) -> (6, 4) -> (6, 5)