我有一个数组A [],其中4个元素A = {8 1 2 4}.如何以最小的成本对其进行排序.标准定义如下 -
一个.可以交换任何2个元素.
湾 任何交换的成本是元素值的总和,如果i交换8和4,则成本为12,结果数组看起来像A = {4 1 2 8},仍然未分类,因此需要更多交换.
C.需要找到一种以最低成本对数组进行排序的方法.
根据我的观察,贪婪将不起作用,就像在每一步中将任何元素以最小成本放置在数组中的排序位置.因此需要DP解决方案.任何人都可以帮忙吗？
交换2和1，然后1和4，然后1和8？或者这是一个普遍问题？
对于更通用的方法，您可以尝试：
如果每对 2 个元素（总和最大）是完美交换，则交换它们（即交换它们会将它们放在正确的位置）。钍
使用最低的元素作为交换的枢轴（通过交换它占据的位置的元素），直到它到达最终位置
那么，你有两种可能：
重复步骤2：使用不在最终位置的最低元素作为枢轴，直到到达最终位置，然后返回步骤3
或者将不在最终位置的最低元素 (l2) 与最低元素 (l1) 交换，重复步骤 2，直到 l1 到达 l2 的最终位置。然后：
完成所有这些后，如果依次执行一些相反的交换（例如，从步骤 2. 到步骤 3.2. 可能会发生这种情况），请将其删除。
仍然有一些事情需要注意，但这已经是一个相当好的近似值了。不过，第一步和第二步应该始终有效，第三步将是在某些边缘情况下需要改进的一步。
所使用的算法示例：
使用 {8 4 5 3 2 7}：（目标数组 {2 3 4 5 7 8}）
步骤 2：2 <> 7, 2 <> 8
数组现在是 {2, 4, 5, 3, 7, 8}
3.1 和 3.2 之间的选择：
3.1 给出 3 <> 5, 3 <> 4
3.2 给出 2 <> 3, 2 <> 5, 2 <> 4, 2 <> 3
3 <> 5, 3 <> 4 是更好的结果
结论：2 <> 7、2 <> 8、3 <> 5、3 <> 4 是最佳答案。
使用 {1 8 9 7 6}（结果数组 {1 6 7 8 9}）
你已经从第三步开始了
3.1 和 3.2 之间的选择：
3.1 给出 6 <> 9, 6 <> 7, 6 <> 8 （总计：42）
3.2 给出 1 <> 6, 1 <> 9, 1 <> 7, 1 <> 8, 1 <> 6 （总计：41）
所以 1 <> 6, 1 <> 9, 1 <> 7, 1 <> 8, 1 <> 6 是最好的结果
| 归档时间： |
|
| 查看次数： |
2437 次 |
| 最近记录： |