javascript - 欧拉项目#345 : Max sum matrix with unique path

Question

基点:我正在寻求有关如何使用动态编程来解决以下问题的帮助。我当前的解决方案有点失控。

问题:从仅组合每个子数组中的一个元素的 NxN 矩阵中找到最大和，必须从每一列中选择元素。 例如: [[1,2], [3,4]] 最大和为 5。因此，矩阵 [0][0] + 矩阵[1][1] 或矩阵[0][1] + 矩阵[1][0]。

应该能够运行 n = 0...30。

我编写了以下具有次优时间复杂度的函数:

var perm = function (values, currentCombo = [], allPerm  = []) {
  if (values.length < 1) {
    allPerm.push(currentCombo);
    return allPerm;
  }
  for (var i = 0; i < values.length; i++) {
    var copy = values.slice(0);
    var value = copy.splice(i, 1);
    perm(copy, currentCombo.concat(value), allPerm);
  }
  return allPerm;
};

var maxSumMatrix = function(matrix){
  var n = matrix.length;
  var options = [];
  for(let i = 0; i < n; i++){
      let row = new Array(n).fill(0);
      row[i] = 1;
      options.push(row);
  }
  var paths = perm(options);
  var accumMax = null;
  for(var i = 0; i < paths.length; i++){
      var sum = null;
      for(var j = 0; j < paths[i].length; j++){
        for(var k = 0; k < paths[i][j].length; k++){
          sum += paths[i][j][k] * matrix[j][k];
        }
        if(accumMax === null || accumMax < sum){
          accumMax = sum;
        }
      }
  }
  return accumMax;
}

因此，“perm”找到解决方案的所有 0,1 排列，然后我将每个可能的解决方案乘以输入矩阵并找到最大答案。

谢谢!

编辑

因此对于以下矩阵:[[1,2,4], [2,-1,0], [2,20,6]]； 最大的和是 26。 来自:矩阵[0][2] + 矩阵[1][0] + 矩阵[2][1]

Answer 1

这是我的处理方法:

const remove = (start, count, list) => {
  var result = list.slice(0);
  result.splice(start, count);
  return result;
}

const removeRow = (row, matrix) => remove(row, 1, matrix);
const removeCol = (col, matrix) => matrix.map(row => remove(col, 1, row)); 
const max = (xs) => Math.max.apply(null, xs);

const maxSum = (matrix) => matrix.length === 1 
  ? max(matrix[0]) 
  : max(matrix[0].map((col, idx) => col + maxSum(removeCol(idx, removeRow(0, matrix)))));

maxSum([
  [1, 2,  4], 
  [2, -1, 0], 
  [2, 20, 6]
]); //=> 26

如果您使用非常大的矩阵，这会遇到递归深度问题。

这做出了各种简化的假设。它们归结为输入是数字方阵的要求。如果不这样做，可能会发生不好的事情。

<小时/>

如果您感兴趣，我首先在 Ramda 中这样做了，因为我就是这么想的。 (我是作者之一。)然后我把它翻译成上面的。

在 Ramda 中，它可能看起来像这样:

const removeRow = curry((row, matrix) => remove(row, 1, matrix));
const removeCol = curry((col, matrix) => map(remove(col, 1), matrix)); 
const highest = (xs) => Math.max.apply(null, xs);

const maxSum = (matrix) => matrix.length == 1 
  ? highest(matrix[0]) 
  : highest(addIndex(map)((col, idx) => col + maxSum(removeCol(idx, removeRow(0, matrix))), matrix[0]));

...您可以在 Ramda REPL 上看到。