0

假设我有一个设备矩阵及其统计数据。帽子，衬衫，裤子，靴子。每个内部数组的大小可以不同，但​​总会有一定数量的内部数组——在本例中为 4。

var array = [
  [1,9,2,8,3],        // hat
  [2,8,3,6],          // shirt
  [1,3],              // pants
  [9,3,2,6,8,2,1,5,2] // boots
]

我想通过矩阵找到最佳路径，然后以这样一种方式删除一个项目，即确定的下一条路线（以及路线的总和）是第一条之后的下一个最佳路线。在这个例子中，[9, 8, 3, 9]最好，对吗？所以我们可以删除9[0] 中的 a 以达到8仅 1 的下降。

我可以总结所有可能的路线并从那里确定它，但内部数组的大小可能比显示的要大得多。

我花了一些时间思考它，并研究了周围。我唯一能看到的是匈牙利算法，但它现在超越了我的数学/计算知识。在这种情况下，这会是最适用的知识吗？它似乎可以满足路线的最低“成本”，但我需要相反。

我的想法，至少作为一个想法：

  1. 拉出每个内部数组中的最高数字，从中创建新数组。对此 [0] 进行排名。
  2. 将每个内部数组中的最大数字与下一个最小数字进行比较。排序每个之间的差异。
  3. 从 #2 中找到的具有最小差异的内部数组中删除最大的数字。
  4. 重复 #1 到 #3。

在上面的示例中，我期望如下所示。

[9, 8, 3, 9]
[8, 8, 3, 9]
[8, 8, 3, 8]
[8, 6, 3, 8]
[8, 6, 3, 6]
[8, 6, 3, 5]

编辑：我想我扼杀了这个问题的解释，让我稍微修正一下。

EDIT2：本质上是跨集的最小损失，仅从一个内部数组中删除一项。

4

1 回答 1

0

更新：我最初误解了你的问题。您随后澄清了这个问题，我在这里提供了一个全新的解决方案。

我使用的策略是将所有子数组中的所有元素展平为一个数组，但这样做的方式是记住它们来自哪个原始子数组。然后我对展平的数组进行排序，首先按值降序排列，然后按子数组编号升序排列。例如，排序后的扁平数组的前 3 个元素将是 [[9,0], [9,3], [8,0],...] 表示来自子数组 0 的值 9，然后是值 9从子数组 3 开始，然后从子数组 0 中取值 8，依此类推。然后我继续遍历列表，获取所需的值，直到达到 n，但为我还没有的任何子数组留出空间选择了一个值。

请注意，此解决方案适用于任意数量的子数组，每个子数组具有任意数量的元素。

const array = [
  [1,9,2,8,3],        // hat
  [2,8,3,6],          // shirt
  [1,3],              // pants
  [9,3,2,6,8,2,1,5,2] // boots
];
for (let n = 0; n < 17; n += 1) {
  const valuesChosen = getTopNBest(array, n);
  console.log(`n = ${n}: ${JSON.stringify(valuesChosen)}`);
}

function getTopNBest(array, n) {
  const numTypes = array.length;
  const allElmtsRanked = [];
  array.forEach((sub, typeNum) => {
    sub.forEach(elmt => {allElmtsRanked.push([elmt, typeNum]);});
  });
  allElmtsRanked.sort((a,b) => b[0] - a[0] !== 0 ? b[0] - a[0] : a[1] - b[1]);
  const valuesChosen = array.map(() => null);
  let totalNumValuesExamined = 0;
  let numSecondaryValuesChosen = 0;
  let numUnrepresentedTypes = numTypes;
  let currPair, currValue, currTypeNum;
  while (numUnrepresentedTypes !== 0 || numSecondaryValuesChosen < n) {
    currPair = allElmtsRanked[totalNumValuesExamined];
    currValue = currPair[0];
    currTypeNum = currPair[1];
    totalNumValuesExamined += 1;
    if (valuesChosen[currTypeNum] === null) {
      valuesChosen[currTypeNum] = currValue;
      numUnrepresentedTypes -= 1;
    } else if (numSecondaryValuesChosen < n) {
      numSecondaryValuesChosen += 1;
      valuesChosen[currTypeNum] = currValue;
    }
  }
  return valuesChosen;
}

您随后问为什么我先按值排序，然后按子数组编号。比较以下两种情况：

var array = [
  [8],
  [9,9,9,9,9],
  [8],
  [8]
]

...相对...

var array = [
  [9,8],
  [9,9],
  [9,8],
  [9,8]
]

如果您只是将这些展平并对展平数组进行排序而不保留有关值来自哪个子数组的任何信息，那么在两种情况下您最终都会得到相同的排序展平数组，即

var sortedFlattenedArray = [9,9,9,9,9,8,8,8]

假设您想要最佳/最佳途径。您现在可以[9,9,9,9]使用任何一种情况，而使用您真正想要的第一种情况[8,9,8,8]。只有当您记住子数组/类型编号时，您才能得到这个，例如：

var sortedFlattenedArray = [[9,1],[9,1],[9,1],[9,1],[9,1],[8,0],[8,2],[8,3]]

因此，当您不再需要任何类型的任何次优值但您仍在寻找特定的最高可能值时，实际策略允许您忽略来自已采样类型的合理高但次优的值类型。

这是另一种看待它的方式。这里的策略允许您对所有原始数组进行展平和排序，但要记住每个元素的来源。这反过来让您在选择路径时可以通过说：“啊，下一个值非常高，这很好，但是等等，它是为了一顶帽子（你只能通过能够阅读它的关联子来知道） -array/type number) 并且我已经检索到我的“次优值”配额，所以我将忽略这个帽子值。但是，我将继续遍历排序的扁平数组以找到a 的最高剩余值我还没有找到任何价值的衬衫（同样，您只能通过读取其关联的子数组/类型编号才能发现）。”

于 2017-01-22T16:29:33.787 回答