《編程之美》讀書筆記15： 4.5 磁帶文件存放優(yōu)化

對(duì)一個(gè)已經(jīng)是最優(yōu)解的排列，記第i個(gè)文件的長度為B_i，被訪問概率為A_i。如果交換第i個(gè)和第i+1個(gè)文件，則平均長度一定不會(huì)變小，交換后，訪問原第i個(gè)文件時(shí)，要多訪問一個(gè)原第i+1文件，長度增加了A_i*B_i+1，而訪問原第i+1個(gè)文件時(shí)，要少訪問一個(gè)原第i個(gè)文件，長度減少了A_i+1*B_i，而訪問這兩個(gè)文件之前和之后的文件，長度沒有改變，故有：

A_i*B_i+1 - A_i+1*B_i >=0 即A_i/B_i >= A_i+1/B_i+1，

由于i可以任意取，因而A₀/B₀ >= A₁/B₁ >= A₂/B₂ >= … >= A_n-1/B_n-1。也就是說，最優(yōu)解一定滿足P[i]/L[i] 按降序排列，而根據(jù)P[i]/L[i]值通過降序排列只能得到唯一確定的排列（只考慮P[i]/L[i]值大小，如果兩個(gè)文件的P[i]/L[i]值相同，它們位置可以互換而不影響），這個(gè)排列必然是最優(yōu)解。因而，原問題等同于“將P[i]/L[i] 降序排列”。

類似題：

“將一個(gè)給定的自然數(shù)數(shù)組，連接起來得到一個(gè)數(shù)，求這個(gè)數(shù)的最大值或最小值”。