你可能感興趣的試題

假定要把長(zhǎng)為l₁，l₂，l_n的n個(gè)程序分布到兩盤磁帶T₁和T₂上，并且希望按照使最大檢索時(shí)間取最小值的方式存放，如果存放在T₁和T₂上的程序集合分別是A和B，那么就希望所選擇的A和B使得max取最小值。一種得到A和B的貪心方法如下：開(kāi)始將A和B都初始化為空，然后一次考慮一個(gè)程序，如果，則將當(dāng)前正在考慮的那個(gè)程序分配給A，否則分配給B。證明無(wú)論是按l₁≤l₂≤，≤l_n或是按l₁≥l₂≥，≥l_n的次序來(lái)考慮程序，這種方法都不能產(chǎn)生最優(yōu)解。

假定要將長(zhǎng)為l₁，l₂，l_n的n個(gè)程序存入一盤磁帶，程序i被檢索的頻率是f_i。如果程序按i₁，i₂，i_n的次序存放，則期望檢索時(shí)間（ERT）是。
①證明按l_i的非降次序存放程序不一定得到最小的ERT。
②證明按f_i的非增次序存放程序不一定得到最小的ERT。
③證明按f_i/l_i的非增次序來(lái)存放程序時(shí)ERT取最小值。