c# - 矩阵中从上到下的最大和路径
问题描述
考虑一个*m 矩阵。假设矩阵中的每个单元格都分配了一个值。我们可以从矩阵第一行的每个单元格开始。允许的移动是对角向左、向下或向右对角线,即从位置开始(i, j)
下一步移动可以是(i+1, j)
、 或(i+1, j+1)
、 或(i+1, j-1)
。(如果索引当然不在数组的范围之外)
再添加一个限制:只允许通过(至少一次)所有列的路径。
找到满足允许移动的元素的最大总和。例如矩阵:
1 15 2
9 7 5
9 2 4
6 9 -1
总和是相等的:
28
因为路径是15+5+2+6=28
。
主要特点是我需要使用动态方法。对于我可以做的所有列没有限制的任务:
var matrix = new int[,]{ { 1, 15, 2 }, //start matrix
{ 9, 7, 5 },
{ 9, 2, 4},
{ 6, 9, -1 } };
long n = matrix.GetLength(0);
long m = matrix.GetLength(1);
var sum = new List<long[]>(); // list [n][m] of maxsums
for (int i = 0; i < n; i++)
{
sum.Add(new long[m].Select(e => e = long.MinValue).ToArray());
}
for (int i = 0; i < m; i++)
{
sum[0][i] = matrix[0, i]; //sums at first line equal first line in matrix
}
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < m; j++)
{
if (j > 0) sum[i + 1][j - 1] = Math.Max(sum[i][j] + matrix[i + 1, j - 1], sum[i + 1][j - 1]); // diagonally left
sum[i + 1][j] = Math.Max(sum[i][j] + matrix[i + 1, j], sum[i + 1][j]); // downwards
if (j < m - 1) sum[i + 1][j + 1] = Math.Max(sum[i][j] + matrix[i + 1, j + 1], sum[i + 1][j + 1]); //diagonally right
}
}
long max = sum[(int)n - 1].Max(); //maximum sum among all paths (answer)
对于同一个矩阵,最大和将等于:
42
因为路径是15+9+9+9=42
Н现在我可以计算所有路径的动态矩阵和有限制的总和吗?
解决方案
一个简单的方法是使用队列。
- 添加第一行
- 对于队列中的每个项目,添加任何其他有效移动
- 完成后,检查它是否是有效的组合
- 检查最后一个最高的
它使用一个迭代器方法、Linq 和队列来返回当前的最佳结果。我建议你做的是研究涉及的部分,逐步检查并检查变量,用于Console.WriteLine
查看正在发生的事情。如果您真的被卡住了,您可以随时询问有关此代码及其作用的更多问题。
队列的想法是,我们将第一行中的每个元素添加为队列中的初始项(这是您给出的规则的前提条件),然后我们去查看队列中的第一个元素,然后从position (x,y) 我们遍历下一行中我们可以合法访问的所有下一个位置。队列还包含访问的列列表和该位置的值。它可以做不同的事情。即我们真的只需要知道所有访问元素的总和和列列表等,这样我们就可以在之后验证路径。
注意:这不是最佳解决方案,它可以通过许多其他方式(并且更优雅)更有效地完成,并且代码更少。但是,它涉及到很多值得理解的常见概念
给定
private static Random _rand = new Random();
// this could be done with linq, however it's easy to see how it works
private static bool IsPathValid(int length, List<int> path)
{
for (var i = 0; i < length; i++)
if (!path.Contains(i))
return false;
return true;
}
迭代器
public static IEnumerable<IEnumerable<(int col, int value)>> FindPath(int[, ] matrix)
{
var queue = new Queue<(int x, int y, List<(int col, int value)> path)>();
// add the first row to the queue
for (var i = 0; i < matrix.GetLength(1); i++)
queue.Enqueue((i, 0, new List<(int col, int value)>()));
// lets keep the higest found
var highest = int.MinValue;
// loop all queue items until none left
while (queue.Any())
{
// get the next item out of the queue
var(x, y, path) = queue.Dequeue();
// add the path we are visiting
path.Add((x, matrix[y, x]));
// if we have looked at all the rows, then time to return
if (y + 1 == matrix.GetLength(0))
{
// get a list of columns visited
var cols = path.Select(x => x.col).ToList();
// check to see if all columns are visited
if (IsPathValid(matrix.GetLength(1), cols))
{
var sum = path.Sum(x => x.value);
// sum the path, if it's not the highest we don't care
if (sum > highest)
{
// we are the highest path so far so let's return it
yield return path;
highest = sum;
}
}
continue;
}
// where ever we are, lets look at all the valid x's in the next row
var start = Math.Max(0, x - 1);
var finish = Math.Min(matrix.GetLength(1) - 1, x + 1);
// add them to the queue
// we inefficiently create a new path, as list is a reference type and we don't want to reuse it
for (var newX = start; newX <= finish; newX++)
queue.Enqueue((newX, y + 1, new List<(int col, int value)>(path)));
}
}
用法
// create a random matrix, make sure there the dimensions are going to produce a result
var y = _rand.Next(2, 5);
var matrix = new int[_rand.Next(y, y + 3), y];
// fill and print the matrix
Console.WriteLine("Matrix");
Console.WriteLine();
for (var i = 0; i < matrix.GetLength(0); i++)
{
for (var j = 0; j < matrix.GetLength(1); j++)
{
matrix[i, j] = _rand.Next(0, 20);
Console.Write(matrix[i, j].ToString().PadLeft(3));
}
Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine("Best Path (column,Value)");
Console.WriteLine();
// get the best, which be the last
var best = FindPath(matrix).Last();
foreach (var item in best)
{
Console.WriteLine(item);
}
// show the result
Console.WriteLine();
Console.WriteLine("= " + best.Sum(x => x.value));
输出
Matrix
14 9 17 0
19 5 11 10
17 12 9 13
3 11 2 5
0 0 12 15
Best Path (column,Value)
(0, 14)
(0, 19)
(1, 12)
(2, 2)
(3, 15)
= 62
其他资源
推荐阅读
- c - 访问已声明函数的参数
- javascript - 更改数组中选定项目的颜色
- r - 使用 R 下载 kaggle 数据集
- python-3.x - 如何在 python 3 Google App Engine 标准环境中进行后台工作?
- jquery - 无法使用自动完成功能获取数据
- android - 如何在 android 的 Cloud Firestore 中更新 arrayList
- r - 基于R中的列表突出显示文本闪亮
- wpf - WPF 绘图图像会留下意外的空像素线
- google-analytics - 谷歌分析中会话和用户范围自定义维度之间的主要区别
- python - 在numpy中获取矩阵的对角线并排除元素