问题是:
您必须使用一系列交换对数组进行升序排序(排列:数字从 1 到 N 的随机顺序)。每个交换都有一个价格，有 5 种价格。编写一个程序，以最小的价格对给定的数组进行排序。 有两种价格:priceByValue 和 priceByIndex。一个种类的所有价格都在 2 个二维数组 N*N 中给出。如何访问价格的示例: 您想要交换值 4 和 7 的排列中的第 2 个和第 5 个元素。此交换的价格将为 priceByValue[4][7] + priceByIndex[2][5]。
所有数组的索引都从 1(而不是从 0)开始计数，以便访问所有价格(排列元素的值从 1 开始):priceByIndex[2][5] 实际上是 priceByIndex[ 1][4] 在代码中。此外，从二维数组中获取价格的索引顺序无关紧要:priceByIndex[i][j] = priceByIndex[j][i] 和 priceByIndex[i][i] 始终等于0.(priceByValue 相同)
价格类型:
价格[i][j] = 0;
价格[i][j] = 1到4*N之间的随机数；
价格[i][j] = |i-j|*6;
价格[i][j] = sqrt(|i-j|) *sqrt(N)*15/4;
价格[i][j] = max(i,j)*3;
当您通过索引访问价格时，i 和 j 是您要从原始数组中交换的元素的索引；当您按值访问价格时，i 和 j 是您要从原始数组交换的元素的值。 (而且总是从1开始计数)
给定的东西: N - 1 到 400 之间的整数，混合数组，priceByIndex 类型，priceByIndex 矩阵，priceByValue 类型，priceByValue 矩阵。 (矩阵的所有元素都来自给定类型)
应“显示在屏幕上”的内容:交换次数、所有交换(仅按索引 - 2 5 表示您交换了第二个和第三个元素)和价格。
由于我仍在学习 C++，所以我想知道对数组进行排序的最有效方法是什么，以便尝试找到成本最小的排序。 可能有一种方法可以访问导致排序数组的一系列交换，并查看哪个价格最低，我需要通过交换值和索引都接近的元素来对数组进行排序，但我不这样做知道怎么做。如果有人能给我一个如何找到最便宜的代码的解决方案，我将不胜感激。提前致谢!
更多:这个问题可能无解，我只是想得到一个接近理想的结果。
最佳答案
动态编程!
将问题视为图表。每个 N 阶乘排列代表一个图顶点，允许的交换只是顶点之间的弧。互换的价格标签就是弧线上的重量。
当您以这种方式看待问题时，可以使用 Dijkstra 算法轻松解决该问题，该算法用于查找从一个顶点到另一个顶点的图形的最低成本路径。
这也称为单对最短路径
关于c++ - 在 C++ 中对排列进行排序的最便宜的方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53138844/