雁過(guò)無(wú)痕

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

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

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。也就是說(shuō)，最優(yōu)解一定滿足P[i]/L[i] 按降序排列，而根據(jù)P[i]/L[i]值通過(guò)降序排列只能得到唯一確定的排列（只考慮P[i]/L[i]值大小，如果兩個(gè)文件的P[i]/L[i]值相同，它們位置可以互換而不影響），這個(gè)排列必然是最優(yōu)解。因而，原問(wèn)題等同于“將P[i]/L[i] 降序排列”。

類似題：

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