如何排序正整数元组以最小化指定Cost成本函数？

这个问题的核心可以通过相邻交换法结合排序不等式来推导最优规则，我们一步步拆解清楚：

步骤1：展开成本函数，明确每对元素的贡献 #

先把你的成本函数展开看看：
$$\text{Cost}(j_1,..., j_n)=\sum_{i=1}^{n-1}T_{j_i}\left( \sum_{k=i+1}^{n}L_{j_k} \right)$$
展开后其实等于所有「排在前面的元组的T」乘以「排在后面的元组的L」的总和，也就是：
$$\text{Cost} = \sum_{1 \leq i < k \leq n} T_{j_i} \cdot L_{j_k}$$
这样问题就简化为：找到一个元组排列，让所有$i<k$的$T_{j_i}L_{j_k}$之和最小。

步骤2：用相邻交换法推导最优排序规则 #

假设现在有两个相邻的元组$x=(T_x, L_x)$和$y=(T_y, L_y)$，我们比较两种排列的成本差异：

• 如果$x$在前、$y$在后：这一对对总成本的贡献是$T_x \cdot L_y$
• 如果$y$在前、$x$在后：这一对对总成本的贡献是$T_y \cdot L_x$

我们要选贡献更小的排列，也就是比较$T_x L_y$和$T_y L_x$：

• 若$T_x L_y < T_y L_x$，则$x$放在$y$前面更好
• 反之，$y$放在$x$前面更好

由于所有$T$、$L$都是正整数，我们可以把不等式变形（两边除以$L_x L_y$，不等号方向不变）：
$$\frac{T_x}{L_x} < \frac{T_y}{L_y}$$
也就是说，我们应该按照$\frac{T}{L}$的升序排列所有元组；如果不想用除法避免精度问题，也可以直接用$T_x L_y < T_y L_x$作为排序的比较规则。

步骤3：联系你提到的点积最小化结论 #

你说的「向量$\mathbf{a}$升序、向量$\mathbf{b}$降序排列最小化点积$\mathbf{a}^T\mathbf{b}$」是排序不等式的逆序和最小结论。我们的成本函数可以间接关联这个结论：

总成本$\sum_{i<k} T_i L_k$加上$\sum_{i>k} T_i L_k$等于$\left( \sum T_i \right)\left( \sum L_i \right) - \sum T_i L_i$，这部分是固定值（和排序无关）。所以最小化$\sum_{i<k} T_i L_k$等价于最大化$\sum_{i>k} T_i L_k$，而$\sum_{i>k} T_i L_k$本质就是把每个元组的$T$和$L$互换后的「顺序和」，这恰好对应逆序和最小的逻辑——按$\frac{T}{L}$升序排列，其实就是让$T$的相对顺序和$L$的相对顺序尽可能逆序，从而最小化目标和。

举个简单例子验证 #

比如有两个元组：$(2,3)$和$(1,4)$

• 按$\frac{T}{L}$排序：$\frac{1}{4}=0.25 < \frac{2}{3}\approx0.67$，顺序为$(1,4)$在前、$(2,3)$在后，成本为$1*3=3$
• 反过来排列的成本为$2*4=8$，显然3更小，符合结论。

内容的提问来源于stack exchange，提问作者AspiringMat