algorithm - 什么是项目列表的“最佳”顺序，以最小化取决于其顺序的成本函数

Question

我正在尝试通过仰卧起坐/俯卧撑等进行锻炼。每次锻炼都会使肌肉群疲劳“x”量。在使肌肉疲劳后，该肌肉将以每秒“r”量的速度恢复（为简单起见是线性的）。

我想订购一套练习，以最大限度地减少任何肌肉在任何时候的最大疲劳。

这感觉就像它可能类似于已解决的标准问题。您能否指出这个已知问题？

标签： algorithmsorting

Answer 1

如果我们谈论 14 个练习，最好的选择可能是使用分支定界法。让我们递归地遍历所有排列。如果我们当前的最大值大于我们之前的上限估计，我们不应该继续这种排列，因为它肯定会更糟。如果我们计算了一个全排列，我们应该更新上限。州的总数是
14! = 8e10，但其中很多会被切断。

它还有助于有一个体面的贪婪解决方案用作初始估计。

我也很确定不存在多项式解决方案，因为我们试图优化的函数太复杂了。