动态规划：当有两个因素需要考虑时如何设计算法？
Dynamic programming: how to design algorithm for when there are two factors to consider?
我有以下问题，对此我只有一点点了解：
考虑磁带存储问题。给定 n 个长度为 l1,...,ln 的文件和访问它们的频率 f1,...,fn，其中所有频率的总和为 1 和 0<fi<1。 "Optimal" 表示最小化这些文件的平均检索时间。例如，如果您有两个文件，每个文件的长度 10, 4 和频率 0.8, 0.2，如果先存储文件 1，则平均检索时间为 10 x 0.8 + 14 x 0.2 = 10.8.
设计一个算法来找到最优顺序并证明它有效。
我的想法：
更大的频率和更大的长度在顺序前面，但哪个因素应该被赋予更高的优先级？
这道题不需要动态规划。这是一个简单的排序问题，稍微有点曲折。
为每个文件查找 frequency / length。这让您知道文件的每个单位长度访问的频率。按降序对这些文件进行排序，因为每个文件的长度 "penalized" 是前一个文件的长度。
证明：
假设顺序是固定的。然后，交换任何两个相邻文件不会影响除交换位置以外的任何其他 li * fi。在交换中调用左边的 x 和另一个 y == x+1。那么，平均检索时间的变化是ly*fx - lx*fy。如果fx/lx < fy/ly，那么ly*fx < lx*fy也就是ly*fx - lx*fy < 0，也就是说平均检索时间减少了。这意味着我们在进行此交换时处于优势地位。每当 fx/lx < fy/ly 时，我们都会继续进行此类交换，并且我们将达到不再可能的地步。这一定是最佳答案。
每当 left < right 时交换相邻的事物类似于降序的冒泡排序，所以我们通常可以使用任何排序来代替。
只让文件长度为升序（l1<l2<l3<l4<...<ln），频率为降序。
因为
average retrieval time =
ART1 =
(l1)*f1 +
(l1+l2)*f2 +
(l1+l2+l3)*f3 +
...
假设我们交换 l1 和 l2。所以我们打破了长度的升序。
ART2 =
(l2)*f1 +
(l2+l1)*f2 +
(l1+l2+l3)*f3 +
...
如果它使 (ART1 < ART2)，它会使情况变得更糟。
看这个。
我们应该检查 ART1-ART2 < 0?
ART1-ART2 =
{ (l1)*f1 + (l1+l2)*f2 }
-
{ (l2)*f1 + (l2+l1)*f2 }
= l1*f1-l2*f1
= (l1-l2)*f1.
根据假设 l1<l2，我们得出结论 ART1-ART2<0。
所以长度应该是升序的。
类似地，如果交换 f1 和 f2，您可以探测频率应该是降序的。
DP 可以工作，但不是解决此问题的好方法，因为虽然检查所有选项的强力方法需要 O(n!) 时间，但 DP 方法花费的时间与不同子问题的数量成正比。比如说，首先我们做出所有可能的 n 个选择，然后我们将剩下 n 个大小为 (n-1) 的子问题，它们都不同。为了使 DP 起作用，主要问题的最优解应该来自子问题的最优解。现在，对于大小为 (n-1) 的问题，假设我们知道解决方案，所以
total average retreival time = (length of first chosen file * 1) + (retrieval time for (n-1) size problem)
由于上述等式，会出现重叠的子问题，但不同子问题的总数将为
nC1 + nC2 + ... nCn = 2^n
仍然呈指数增长。
所以，DP 会降低复杂性，但问题的性质仍然是指数级的。
我有以下问题，对此我只有一点点了解：
考虑磁带存储问题。给定 n 个长度为 l1,...,ln 的文件和访问它们的频率 f1,...,fn，其中所有频率的总和为 1 和 0<fi<1。 "Optimal" 表示最小化这些文件的平均检索时间。例如，如果您有两个文件，每个文件的长度 10, 4 和频率 0.8, 0.2，如果先存储文件 1，则平均检索时间为 10 x 0.8 + 14 x 0.2 = 10.8.
设计一个算法来找到最优顺序并证明它有效。
我的想法： 更大的频率和更大的长度在顺序前面，但哪个因素应该被赋予更高的优先级？
这道题不需要动态规划。这是一个简单的排序问题，稍微有点曲折。
为每个文件查找 frequency / length。这让您知道文件的每个单位长度访问的频率。按降序对这些文件进行排序，因为每个文件的长度 "penalized" 是前一个文件的长度。
证明：
假设顺序是固定的。然后，交换任何两个相邻文件不会影响除交换位置以外的任何其他 li * fi。在交换中调用左边的 x 和另一个 y == x+1。那么，平均检索时间的变化是ly*fx - lx*fy。如果fx/lx < fy/ly，那么ly*fx < lx*fy也就是ly*fx - lx*fy < 0，也就是说平均检索时间减少了。这意味着我们在进行此交换时处于优势地位。每当 fx/lx < fy/ly 时，我们都会继续进行此类交换，并且我们将达到不再可能的地步。这一定是最佳答案。
每当 left < right 时交换相邻的事物类似于降序的冒泡排序，所以我们通常可以使用任何排序来代替。
只让文件长度为升序（l1<l2<l3<l4<...<ln），频率为降序。
因为
average retrieval time =
ART1 =
(l1)*f1 +
(l1+l2)*f2 +
(l1+l2+l3)*f3 +
...
假设我们交换 l1 和 l2。所以我们打破了长度的升序。
ART2 =
(l2)*f1 +
(l2+l1)*f2 +
(l1+l2+l3)*f3 +
...
如果它使 (ART1 < ART2)，它会使情况变得更糟。
看这个。
我们应该检查 ART1-ART2 < 0?
ART1-ART2 =
{ (l1)*f1 + (l1+l2)*f2 }
-
{ (l2)*f1 + (l2+l1)*f2 }
= l1*f1-l2*f1
= (l1-l2)*f1.
根据假设 l1<l2，我们得出结论 ART1-ART2<0。
所以长度应该是升序的。
类似地，如果交换 f1 和 f2，您可以探测频率应该是降序的。
DP 可以工作，但不是解决此问题的好方法，因为虽然检查所有选项的强力方法需要 O(n!) 时间，但 DP 方法花费的时间与不同子问题的数量成正比。比如说，首先我们做出所有可能的 n 个选择，然后我们将剩下 n 个大小为 (n-1) 的子问题，它们都不同。为了使 DP 起作用，主要问题的最优解应该来自子问题的最优解。现在，对于大小为 (n-1) 的问题，假设我们知道解决方案，所以
total average retreival time = (length of first chosen file * 1) + (retrieval time for (n-1) size problem)
由于上述等式，会出现重叠的子问题，但不同子问题的总数将为
nC1 + nC2 + ... nCn = 2^n
仍然呈指数增长。
所以，DP 会降低复杂性，但问题的性质仍然是指数级的。