計(jì)算機(jī)算法基礎(chǔ)第三版_課后習(xí)題答案-文庫(kù)吧資料
2025-06-29 17:33本頁(yè)面
【正文】 應(yīng)為19，所以得證。一種得到A和B的貪心方法如下：開(kāi)始將A和B都初始化為空，然后一次考慮一個(gè)程序，如果=min{,}，則將當(dāng)前正在考慮的那個(gè)程序分配給A，否則分配給B。命題得證。證明：只需證明結(jié)論③是正確的即可，現(xiàn)證明如下： 假設(shè),…, 按照/的非增次序存放，即/≥/≥…≥/，則得到 ERT=[+(+)+…+(++…+ ]/假設(shè)該問(wèn)題的一個(gè)最優(yōu)解是按照,…, 的順序存放，并且其期望檢索式件是，我們只需證明≤，即可證明按照/的非增次序存放得到的是最優(yōu)解。② 證明按的非增次序存放程序不一定得到最小的ERT。．假定要將長(zhǎng)為,…, 的n個(gè)程序存入一盤(pán)磁帶，程序i被檢索的頻率是。證明：當(dāng)按照/的非增次序考慮物品存放背包時(shí)，如果所裝入的物品恰能裝滿背包時(shí)，易證為最優(yōu)解，否則未必是最優(yōu)解。求解此問(wèn)題的一種貪心策略是：按/的非增次序考慮這些物品，只要正被考慮的物品能裝進(jìn)的就將其裝入背包。解：① 按照/的非增序可得(/，/，/，/，/，/，/)= (6,5,9/2,3,3,5/3,1) W的次序?yàn)?1,2,4,5,1,3,7),解為(1,1,1,1,1,2/3,0) 所以最優(yōu)解為：（1,2/3,1,0,1,1,1）FO(I)=166/3② 按照Pi的非增次序輸入時(shí)得到(,)= (18,15,10,7,6,5,3)，對(duì)應(yīng)的(,)= (4,5,2,7,1,3,1)解為(1,1,1,4/7,0,0,0)所以FG(I)的解為（1,0,1,4/7,0,1,0）FG(I)=47，所以FO(I)/ FG(I)=166/141.③ 按照的非降次序輸入時(shí)得到(,)=(1,1,2,3,4,5,7)相應(yīng)的(,)=(6,3,10,5,18,15,7) 解為(1,1,1,1,1,4/5,0)則FW(I)的解為（1,1,4/5,0,1,1,1）FW(I)=54，所以FO(I)/ FW(I)=83/81.．（0/1背包問(wèn)題） 極大化 約束條件 xi=0或1 1≤i≤n這種背包問(wèn)題稱為0/1背包問(wèn)題。設(shè)FG(I)是物品按的非增次序輸入時(shí)由GREEDYKNAPSACK所生成的解，F(xiàn)O(I)是一個(gè)最優(yōu)解。P=(A11+A22)(B11+B22) T=(A11+A12)B22Q=(A21+A22)B11 U=(A21A11)(B11+B12)R=A11(B12B22) V=(A12A22)(B21+B22)S=A22(B21B11)C11=P+ST+V=(A11+A22)(B11+B22) +A22(B21B11) (A11+A12)B22 +(A12A22)(B21+B22)=A11B11+A22B11+A11B22+A22B22+A22B21A22B11A11B22A12B22+A12B21+A12B22A22B21A22B22=A11B11 +A12B21C12=R+T= A11B12A11B22 +A11B22+A12B22= A11B12 +A12B22C21=Q+S= A21B11+A22B11 +A22B21A22B11= A21B11 +A22B21C22=P+RQ+U=(A11+A22)(B11+B22)+A11(B12+B22)(A21+A22)B11 +(A21A11)(B11+B12)=A11B11+A22B11+A11B22+A22B22+A11B12A11B22A21B11A22B11+A21B11+A21B12A11B11A11B12=A22B22+A21B12① 求以下情況背包問(wèn)題的最優(yōu)解，n=7，m=15，=(10,5,15,7,6,18,3)和=(2,3,5,7,1,4,1)。2*length if length n then FOR j = 1 TO n DO Rj←Xj else MPass（X，n，length．R）. length172。i＋2*length ） ． MP3 [處理余留的長(zhǎng)度小于2*length的子文件] IF i+length–1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1