关于从2D阵列创建排序路径列表，我需要知道什么

Question

假设我有一个设备及其统计数据的矩阵。帽子，衬衫，裤子，靴子。每个内部数组的大小可以不同，但总是会有一定数量的内部数组——在本例中为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]是最好的，对吗？因此，我们可以在[0]中移除一个9，以达到仅给出1的下降的8。

我可以汇总所有可能的路线并从中确定，但内部阵列的大小可能比显示的要大得多。

我花了一些时间思考，并四处研究。我唯一能看到的是匈牙利算法，但它已经超过了我现在的数学/compsci知识。在这种情况下，这是最适用的知识吗？这似乎是为了满足一条路线的最低"成本"，但我需要相反的成本。

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

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]

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

第2版：本质上是集合间的最小损失，只从一个内部数组中删除一个项目。

Answer 1

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

我使用的策略是将所有子数组中的所有元素扁平化为单个数组，但这样做的方式要记住它们来自哪个原始子数组。然后，我对扁平数组进行排序，首先按值降序排列，然后按子数组编号升序排列。例如，排序后的扁平数组的前3个元素将是[[9,0]、[9,3]、[8,0]、…]表示来自子阵列0的值9，然后是来自子阵列3的值9、然后是来自于子阵列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]]

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

这是另一种看待它的方法。这里的策略允许您对所有原始数组进行扁平化和排序，但请记住每个元素来自。这反过来又让你在选择途径时有选择性，"啊，下一个值很高，这很好，但等一下，它是一顶帽子(你只能通过读取它的相关子数组/类型号才能知道)，我已经检索到了我的‘次优值’配额，所以我会忽略这个帽子值。但是，我会继续在排序后的扁平数组中移动，找到衬衫的最高剩余值(同样，你只能通过读取其关联的子数组/类型号来发现)，我仍然没有找到任何值。">