得到的矩阵元素的组合中的至少总和 [英] Get least sum of a combination of matrix elements

问题描述

昨天，我的一个朋友想出了一个问题，问我找到了解决办法。

问题

我有一个矩阵（n×m个）。我需要找出至少总和我可以从这些矩阵元素产生。

的条件是：

• 在只计算应该从左上角的单元开始。和
• 在右下角的单元格应该结束了。
• 的算法应该指望所有可能的路径
• 在这种方式，我需要找到最可能的总和。

挣扎了几个小时后，我能够找到这样的模式。但我不知道如何在code实现它。

下面是我的方式：

我如何实现这一点？

编辑：

  $成本=阵列（）;
为（$ x = 0; $ X＆LT; $行; $ X ++）{
    $成本[0] [$ X] = $矩阵[0] [$ X]
    为（$ Y = 1; $ Y＆LT; $ COLS; $ Y ++）{
        $成本[$ Y] [0] = $矩阵[$ Y] [0];
    }
}
为（$ X = 1; $ X＆LT; $行; $ X ++）{
    为（$ Y = 1; $ Y＆LT; $ COLS; $ Y ++）{
        $成本[$ X] [$ Y] = INTVAL（$矩阵[$ X] [$ Y]）+分（INTVAL（$成本[$ X  -  1] [$ Y]），INTVAL（$成本[$ X ] [$ Y  -  1]））;
    }
}
 

矩阵阵列我想：

 阵列（2）{[0] =＆GT;阵列（3）{[0] =＆GT;串（1）3[1] =＆GT;串（2）44[2] =＆GT;字符串（2）75} [1] =＆GT;阵列（3）{[0] =＆GT;字符串（2）21[1] =＆GT;串（2）98[2] =＆GT;字符串（2）60}}
 

结果：

 阵列（3）{[0] =＆GT;阵列（2）{[0] =＆GT;串（1）3[1] =＆GT;串（2）44} [1] =＆GT;阵列（3）{[0] =＆GT;字符串（2）21[1] =＆GT; INT（119）[2] =＆GT; INT（0）} [2] =＆GT;阵列（1）{[0] =＆GT;空值 } }
 

解决方案

看来你可以只在向右和向下的方向。对于这种情况下的（以其它方式使用寻路算法）的注意，你可以每一个细胞或者来自上层的细胞或左边的单元格。最便宜的路径向此细胞将是最小，从这些值。因此，DP解决方案可能看起来像（伪code）：

看到这里的更正

 成本[0,0] =矩阵[0,0]
对于x = 1至COLS  -  1
   成本[0中，x] =矩阵[0，x]中+成本[0中，x-1] //第0行
为Y = 1的行 -  1
   成本[Y，0] =矩阵[Y，0] +成本[Y-1，0] //第0列
//第0行，第0列的合适的填充

为Y = 1的行 -  1
   对于x = 1至COLS  -  1
      成本[Y，X] =矩阵[Y，X] +闵（成本[Y-1，x]中，费用[Y，X-1]）
 

那么成本[N-1，N-1]是你所需要的。

Yesterday one of my friend came with a problem, asking me to find the solution.

The problem

I have a matrix(n x m). I need to find out the least sum what I can produce from those matrix element.

The condition is :

• Counting should only start from the top left cell. And
• Should end at the bottom right cell.
• The algorithm should count all possible paths
• In this way I need to find the possible least sum.

After struggling for a few hours, I'm able to find a pattern for this. But I don't know how to implement it in code.

Here is my pattern :

How can I implement this?

Edit :

$Cost = array();
for ($x = 0; $x < $rows; $x++) {
    $Cost[0][$x] = $matrix[0][$x];
    for ($y = 1; $y < $cols; $y++) {
        $Cost[$y][0] = $matrix[$y][0];
    }
}
for ($x = 1; $x < $rows; $x++) {
    for ($y = 1; $y < $cols; $y++) {
        $Cost[$x][$y] = intval($matrix[$x][$y]) + min(intval($Cost[$x - 1][$y]), intval($Cost[$x][$y - 1]));
    }
}

Matrix array I'm Trying :

array(2) { [0]=> array(3) { [0]=> string(1) "3" [1]=> string(2) "44" [2]=> string(2) "75" } [1]=> array(3) { [0]=> string(2) "21" [1]=> string(2) "98" [2]=> string(2) "60" } }

Result :

array(3) { [0]=> array(2) { [0]=> string(1) "3" [1]=> string(2) "44" } [1]=> array(3) { [0]=> string(2) "21" [1]=> int(119) [2]=> int(0) } [2]=> array(1) { [0]=> NULL } }

解决方案

It seems that you can go only in right and down directions. For this case (otherwise use path finding algorithms) note that you can come in every cell either from upper cell or from left cell. The cheapest path to this cell will be minimum from these values. So DP solution may look like (pseudocode):

see corrections here

Cost[0, 0] = matrix[0, 0]  
for x = 1 to cols - 1 
   Cost[0, x] = matrix[0, x] + Cost[0, x-1]  //0th row
for y = 1 to rows - 1  
   Cost[y, 0] = matrix[y, 0] + Cost[y-1, 0] //0th column
//proper filling of 0th row and 0th column

for y = 1 to rows - 1
   for x = 1 to cols - 1 
      Cost[y, x] = matrix[y, x] + Min(Cost[y-1, x], Cost[y, x-1]) 

then Cost[n-1, n-1] is what you need

这篇关于得到的矩阵元素的组合中的至少总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！