資源描述：
《貪心算法的實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、福建工程學(xué)院計算機與信息科學(xué)系實驗報告2012–2013學(xué)年第一學(xué)期任課老師：章靜課程名稱結(jié)構(gòu)化程序設(shè)計班級座號姓名實驗題目實驗2貪心算法設(shè)計技術(shù)的應(yīng)用實驗時間實驗開始日期：2012-12-11報告提交日期：2012-12-25實驗?zāi)康?、要求一、算法設(shè)計技術(shù)貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。例1：找零錢，一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為25分、10美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時所采用的貪心策
2、略如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應(yīng)使零錢總數(shù)超過最終所需的數(shù)目。假設(shè)需要找給小孩67美分，首先入選的是兩枚25美分的硬幣，第三枚入選的不能是25美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過67美分），第三枚應(yīng)選擇10美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。其實，從“貪心策略”一詞我們便可以看出，貪心策略總是做出在當(dāng)前看來是最優(yōu)的選擇，也就是說貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問題自身的特性決定了該題運用貪心策略可以得到最優(yōu)解或較優(yōu)解?？梢宰C明采用上述貪心算
3、法找零錢時所用的硬幣數(shù)目的確最少。利用貪心策略解題，必須考慮兩個問題，首先，問題是否適合于用貪心策略求解；其次，是在確定了可以用貪心策略之后，如何選擇一個貪心標(biāo)準(zhǔn)，才能保證得到問題的最優(yōu)解。例2：背包問題?，F(xiàn)有載重為M公斤的背包和n種貨物。第i種貨物的重量為Wi，它的總價值為Pi，假定M、Wi、Pi均為整數(shù)。采用怎樣的裝貨方法，才能使裝入背包的貨物總價值達(dá)到最大?【分析】當(dāng)貨物總重量∑Wi小于或等于M時，把所有貨物裝入，總價值就達(dá)到最大。因此，關(guān)鍵是解決當(dāng)總重量大于M時裝貨的方法。我們先從一個具體例子入手來研究一下本題的特點。設(shè)n=3；M=20。W1=15W2=10W3=8P1=18P2=15
4、P3=10有幾種可能解（設(shè)Xi為第i種貨物所取的重量）：X1X2X3總重∑Xi總價值∑PiXi/Wi(1)10552025.75(2)101002027(3)21082027.4(4)40162022.4顯然第3個解總價值最大。5/6上述可能解是采用窮舉方法試探所得眾多可能解中的4種，這在具體的程序編制和實現(xiàn)過程中相當(dāng)麻煩，且在時間復(fù)雜度上很難承受，是否可以尋找到一種簡單而又時間效率高的方法呢？下面用貪心策略來解此題。首先應(yīng)該確定貪心的量度標(biāo)準(zhǔn)。一種設(shè)想是按價值大小作為標(biāo)準(zhǔn)，先放價值最大的貨物，再放價值次大的貨物。即按價值從大到小順序放置。則有方案：∵P1>P2>P3∴放置順序為X1，X2，X
5、3取X1＝15，X2＝5，得到∑P＝X1P1+X1P2＝18＋7.5=25.5得到的不是最優(yōu)解。表明用價值作為量度標(biāo)準(zhǔn)是錯誤的。原因是什么呢?原因是價值大的重量也大，我們按價值大的先放，造成重量消耗過快。由此啟發(fā)我們用Pi/Wi（單位重量價值）來作量度標(biāo)準(zhǔn)，則有：U1=P1/W1=1.2U2=P2/W2=1.5U3=P3/W3=1.25因此放置順序是X2，X3，X1，即有：X2=10X3=8X1=2∑XiUi=15+10+2.4=27.4這才是最優(yōu)解。下面給出算法的簡單描述：Begin讀入數(shù)據(jù)；計算貨物的單位重量價值Ti=Pi/Wi，并將它們從大到小排序；依次選擇單位重量較大的貨物裝入背包，直
6、至不能裝入；輸出最大價值總和S和裝貨方案；End;二、實驗題目1．利用貪心策略解決背包問題。現(xiàn)有載重為M公斤的背包和n種貨物。第i種貨物的重量為Wi，它的總價值為Pi，假定M、Wi、Pi均為整數(shù)。設(shè)計程序給出裝貨方法，使裝入背包的貨物總價值達(dá)到最大。2．設(shè)計實現(xiàn)超市收銀程序，假設(shè)顧客在超市購買各種商品，來到收銀臺結(jié)賬，收銀員具有面值為100，20，10，5和1元的紙幣和各種面值為5角、2角、1角的硬幣。設(shè)計程序計算顧客各種所買商品的錢數(shù)，并根據(jù)顧客所付的錢數(shù)輸出零錢的數(shù)目及要找的各種貨幣的數(shù)目。三、實驗要求1．該實驗的課內(nèi)學(xué)時是4個課時。2．題目1必須完成。3．題目1在完成上述基本功能的前提下
7、，有能力的同學(xué)可以完成題目2。實驗步驟與內(nèi)容5/6按如下順序?qū)懀?、主要設(shè)計思想:(1)第一題的關(guān)鍵是裝入背包的貨物的性價比要最高。按照性價比的順序從高到低依次排列，同時還要注意背包的載重量。(2)第二題的關(guān)鍵是找零，將零錢一步一步取整就可以了。2、主要數(shù)據(jù)結(jié)構(gòu)及其解釋：第一題：（1）&&&&&&&&對單位重量值進(jìn)行冒泡排序&&&&&&&&Sort(intn)（2）&&&&&將排好序的貨物依次放入
