贪心问题请教
假定要将长为l1,l2,l3.....ln的n个程序存入一盘磁带,程序i被检索的频率是fi,如果程序按i1,i2,i3....in的次序存放,则期望的检索时间是:
j
[E(f(i(j))E l(i(k))]/E fi
j k=1
注:E代表累加,f(i(j)))中的括号是代表下标的...就象l1,l2的1 2..
证明:按fi/li的非增次序来存放程序时得到ERT的最小值..
各位大虾给个贪心的思路..谢谢了
[解决办法]
大体思路是：假定有一个最优解，通过把最优解逐步变为贪心解，并且每一步都不会提高检索时间。
具体证明：
假定有一个最优解不同于贪心解，那么可以证明在最优解中，必然存在着1<=i<=n，使得fi/li < f(i+1)/l(i+1)
把i和i+1互换，不会影响到i之前，也不会影响到i+1之后
所以把i和i+1互换前后检索时间之差={fi*li + f(i+1)*[li+l(i+1)]} - {f(i+1)*l(i+1) + fi*[li+l(i+1)]} = f(i+1)*li - fi*l(i+1) > 0
所以互换前后降低了检索时间，最优解仍然是最优解。
最多只需要n*n/2次互换可以把一个最优解换成贪心解，所以问题解决。
