algorithm - 有什么更好的方法来解决这个(贪心？)问题

Question

假设我有 n 个盒子，每个盒子里面都有一些值 b[i] .我可以保证对一组框进行排序，使得 b[1] <= b[2] <= ... <= b[n] .我也可以保证有一个元素 b[i] = x我想找到哪个盒子 x在里面。问题是打开每个盒子b[i]有一些成本c[i] .

问题是如何最小化寻找 x 的总成本？我的直觉方法是对 b[i] 进行二分查找。的。这减少了操作总数(因为我得到了 O(logn) 比较)但我无法确切地看到这将如何最小化总成本。

显然，只选择最便宜的盒子并继续下去是行不通的，因为在最坏的情况下我会打开每个盒子。关于如何改进这一点或如何证明我的方法是最优的/不是最优的，有什么想法吗？

Answer 1

使用动态规划寻找最佳决策树。设 T(i, j) 是搜索位置 i..j 的最坏情况成本。然后

T(i, j) = { 0,                                              if i > j;
          { min_{k=i}^j (c[k] + max(T(i, k-1), T(k+1, j))), otherwise.

记住每个区间的 k 的最佳选择。

运行时间是 O(n^3)，使用 Knuth 的技巧可以减少到 O(n^2) optimal BST .