計(jì)算機(jī)算法基礎(chǔ)第三版_課后習(xí)題答案(編輯修改稿)
2025-07-20 17:33 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ② 按照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)題。它要求物品或者整件裝入背包或者整件不裝入。求解此問(wèn)題的一種貪心策略是：按/的非增次序考慮這些物品，只要正被考慮的物品能裝進(jìn)的就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。證明：當(dāng)按照/的非增次序考慮物品存放背包時(shí)，如果所裝入的物品恰能裝滿背包時(shí)，易證為最優(yōu)解，否則未必是最優(yōu)解。可舉例如下：設(shè)n=3，M=6，（, , ）=(3,4,8)，（, , ）=(1,2,5)，按照/的非增序得到（/, /, /）=(3,2,)，則其解為（1,1,0），而事實(shí)上最優(yōu)解是(1,0,1)，問(wèn)題得證。．假定要將長(zhǎng)為,…, 的n個(gè)程序存入一盤磁帶，程序i被檢索的頻率是。如果程序按,…, 的次序存放，則期望檢索時(shí)間（ERT）是① 證明按的非降次序存放程序不一定得到最小的ERT。② 證明按的非增次序存放程序不一定得到最小的ERT。③ 證明按/的非增次序來(lái)存放程序時(shí)ERT取最小值。證明：只需證明結(jié)論③是正確的即可，現(xiàn)證明如下： 假設(shè),…, 按照/的非增次序存放，即/≥/≥…≥/，則得到 ERT=[+(+)+…+(++…+ ]/假設(shè)該問(wèn)題的一個(gè)最優(yōu)解是按照,…, 的順序存放，并且其期望檢索式件是，我們只需證明≤，即可證明按照/的非增次序存放得到的是最優(yōu)解。易知=[+(+)+…+(++…+ )]/從前向后考察最優(yōu)解中的程序，不妨設(shè)程序是第一個(gè)與其相鄰的程序存在關(guān)系/≤/，則交換程序和程序，得到的期望檢索時(shí)間記為=≤0 ≤顯然也是最優(yōu)解，將原來(lái)的最優(yōu)解中所有這樣類似于反序?qū)Φ某绦蚧Q位置，得到的解不比原來(lái)的最優(yōu)解差，所以最終變換后得到的解也是最優(yōu)解，而最終的解恰是程序按/的非增次序來(lái)存放得到的順序。命題得證。,…, 的n個(gè)程序分布到兩盤磁帶和上，并且希望按照使最大檢索時(shí)間取最小值的方式存放，即，如果存放在和上的程序集合分別是A和B，那么就希望所選擇的A和B使得max{,}取最小值。一種得到A和B的貪心方法如下：開始將A和B都初始化為空，然后一次考慮一個(gè)程序，如果=min{,}，則將當(dāng)前正在考慮的那個(gè)程序分配給A，否則分配給B。證明無(wú)論是按≤≤…≤或是按≥≥…≥的次序來(lái)考慮程序，這種方法都不能產(chǎn)生最優(yōu)解。證明：按照≤≤…≤存放不會(huì)得到最優(yōu)解，舉例如下：3個(gè)程序（a,b,c）長(zhǎng)度分別為（1,2,3），根據(jù)題中的貪心算法，產(chǎn)生的解是A={a,c}B=，則max{,}=4，而事實(shí)上，最優(yōu)解應(yīng)為3，所以得證.按照≥≥…≥的次序存放也不會(huì)得到最優(yōu)解，舉例如下：5個(gè)程序（a,b,c,d,e）長(zhǎng)度分別為（10,9,8,6,4）根據(jù)題中的貪心算法，產(chǎn)生的解是A={a,d,e}B={b,c}，則max{,}=20，而事實(shí)上，最優(yōu)解應(yīng)為19，所以得證。.①當(dāng)n=7，=(3,5,20,18,1,6,30) 和=(1,3,4,3,2,1,2)時(shí)，？ ② 。這里，假定作業(yè)I的效益0，要用的處理時(shí)間0，限期≥.解：①根據(jù)的非增排序得到(,,)=(30,20,18,6,5,3,1)，對(duì)應(yīng)的期限為(2,4,3,1,3,1,2)，：(1)=7(1)=7,J(2)=3(1)=7,J(2)=4,J(3)=3(1)=6, J(2)=7,J(3)=4,J(4)=3；②證明：顯然即使0（≥），如果J中的作業(yè)可以按照s的次序而又不違反任何一個(gè)期限來(lái)處理，即對(duì)s次序中的任一個(gè)作業(yè)k，應(yīng)滿足 ≥，則J就是一個(gè)可行解。下面證明如果J是可行解，則使得J中的作業(yè)可以按照,…, 排列的序列s處理而又不違反任何一個(gè)期限。因?yàn)镴是可行解，則必存在=…，使得對(duì)任意的，都有≥，我們?cè)O(shè)s是按照≤≤,…,≤排列的作業(yè)序列。假設(shè)185。s，那么令a是使185。的最小下標(biāo)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1