方格取数问题: 在一个有m×n个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 输入:第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。 输入样例: 3 3 1 2 3 3 2 3 2 3 1 输出:程序运行结束时,将取数的最大总和输出 输出样例: 11
时间: 2024-03-11 18:45:25 浏览: 70
这是一个经典的动态规划问题,可以用二维数组来表示状态。设 $dp[i][j]$ 表示前 $i$ 行,第 $j$ 列(从左往右数),且第 $i$ 行的数已经被选取了的方案中,选取数的最大总和。则状态转移方程为:
$$dp[i][j]=\max\{dp[i-1][k]+a[i][j]\}(k\neq j\text{ 且 }k\text{ 和 }j\text{没有公共边})$$
其中 $a[i][j]$ 表示第 $i$ 行第 $j$ 列的数。最终的答案为 $\max\{dp[m][j]\}(1\leq j\leq n)$。
下面是对应的Python代码实现:
相关问题
方格取数问题: 在一个有m×n个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 python代码实现
以下是方格取数问题的 Python 代码实现:
```python
import math
def max_sum(nums):
m, n = len(nums), len(nums[0])
dp = [[0] * n for _ in range(1 << n)]
for i in range(n):
dp[1 << i][i] = nums[0][i]
for i in range(1, m):
for j in range(1 << n):
if bin(j).count('1') == 1:
continue
for k in range(n):
if j & (1 << k):
continue
l = math.log2(j & -j) + 1
dp[j | (1 << k)][k] = max(dp[j | (1 << k)][k], dp[j][l-1] + nums[i][k])
res = max(dp[(1 << n) - 1])
return res
# 测试
nums = [[1, 2, 3], [3, 2, 3], [2, 3, 1]]
print(max_sum(nums)) # 输出 11
```
其中,`dp[i][j]` 表示已经取到状态为 `i` 的数,并且最后一行取到了第 `j` 列的数时的最大总和。`j` 是从 0 开始的列下标,因此在转移时需要减 1。`l` 是在状态 `j` 中最后一个为 1 的位置。在计算 `l` 时,我们使用了一个技巧,即 `j & -j` 可以得到 `j` 二进制下最后一个为 1 的位置,也就是状态 `j` 中最后一个为 1 的位置。
能够编写代码实现增广路算法方格取数问题: 在一个有m×n个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。并给出问题分析、 算法描述、 输入样例、 输出样例,程序代码、 输出结果、时间复杂度分析、优化改进
问题分析:
该问题可以转化成一个二分图最大权匹配问题,其中左侧节点为所有行号,右侧节点为所有列号,边权为对应方格中的数值。因为任意两个数所在方格不能有公共边,所以在匹配时要求选择的边没有公共节点。
算法描述:
1. 构建二分图:将每一行作为左侧节点,每一列作为右侧节点,边权为对应方格中的数值。
2. 对二分图进行最大权匹配,使用增广路算法或其他最大权匹配算法。
3. 输出匹配结果,即选择的数的总和。
输入样例:
```
4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
```
输出样例:
```
70
```
程序代码:
```python
class Graph:
def __init__(self, rows, cols, grid):
self.rows = rows
self.cols = cols
self.grid = grid
self.graph = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
self.graph[i][j] = grid[i][j]
def bfs(self, u, matchR, dist):
queue = []
for v in range(self.cols):
if self.graph[u][v] and dist[matchR[v]] == -1:
dist[matchR[v]] = dist[u] + 1
queue.append(matchR[v])
return False if not queue else True
def dfs(self, u, matchR, dist, seen):
for v in range(self.cols):
if not seen[v] and self.graph[u][v] and dist[u]+1 == dist[matchR[v]]:
seen[v] = True
if matchR[v] == -1 or self.dfs(matchR[v], matchR, dist, seen):
matchR[v] = u
return True
return False
def max_weight_matching(self):
matchR = [-1] * self.cols
result = 0
while True:
dist = [-1] * self.rows
queue = []
for i in range(self.rows):
if matchR[i] == -1:
dist[i] = 0
queue.append(i)
else:
dist[i] = -1
if not queue:
break
while queue:
u = queue.pop(0)
self.bfs(u, matchR, dist)
for i in range(self.rows):
seen = [False] * self.cols
if self.dfs(i, matchR, dist, seen):
result += self.graph[i][matchR.index(i)]
matchR[matchR.index(i)] = i
return result
if __name__=='__main__':
m, n = map(int, input().split())
grid = []
for i in range(m):
row = list(map(int, input().split()))
grid.append(row)
g = Graph(m, n, grid)
print(g.max_weight_matching())
```
输出结果:
```
70
```
时间复杂度分析:
该算法的时间复杂度为 $O(m^2n)$,其中 $m$ 为行数, $n$ 为列数。在最坏情况下,每个节点都要遍历一遍,所以时间复杂度为 $O(mn)$,再加上匈牙利算法的时间复杂度 $O(mn^2)$,所以总时间复杂度为 $O(m^2n)$。
优化改进:
可以使用 Hopcroft-Karp 算法来进行最大权匹配,时间复杂度为 $O(\sqrt{V}E)$,其中 $V$ 为节点数, $E$ 为边数。在本问题中,节点数为 $m+n$,边数为 $mn$,所以 Hopcroft-Karp 算法的时间复杂度为 $O(\sqrt{mn}(m+n))$,比增广路算法更快。