版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第4次實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間11.14下午地點(diǎn)四合院實(shí)驗(yàn)名稱(chēng)貪心算法實(shí)驗(yàn)(求解背包問(wèn)題)實(shí)驗(yàn)?zāi)康?通過(guò)上機(jī)實(shí)驗(yàn),要求掌握貪心算法的問(wèn)題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)。.設(shè)計(jì)程序,利用貪心算法求解背包問(wèn)題,輸出相應(yīng)結(jié)果,笄計(jì)算出程序運(yùn)行 所需要的時(shí)間。實(shí)驗(yàn)原理給定幾組數(shù)據(jù),利用貪心算法的思想,將物品裝入背包并使得其價(jià)值最大。實(shí)驗(yàn)步驟計(jì)算每種物品單位重量的價(jià)值Vi/Wi.依貪心選擇策略,將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后,背包內(nèi)的物品總重量未超過(guò)C,則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去,直到背包裝滿(mǎn)為止。關(guān)鍵
2、代碼/按價(jià)重比冒泡排序void sort(node Node,int M)int i,j;node temp;for(i=0;iM-1;i+)for(j=i+1;jM;j+)if(Nodei.value/(float)Nodei.weight)Nodej.value/(float)Node j.weight)temp=Nodei;Nodei=Nodej;Nodej=temp;printf(物品的價(jià)重比從高到低依次排列為:n);for(i=0;iM;i+)printf(%.2f ,Nodei.value);printf(n);for(i=0;iM;i+)printf(%.2f ,Nodei.we
3、ight);/裝包主要方法及輸出void pack(node Node,int M)int i,j=1;printf(nn選中物品的價(jià)格為:n);for(i=0;iM;i+)if(Nodei.weight+curweight).00 B. 00 8. 00進(jìn)中物品的價(jià)格為第1次選擇后,價(jià)格為;7. 00露2次山罩后,價(jià)格為,1620案2次選擇后,價(jià)格為:23.00SU ser ss (nmyDes ktop01 國(guó)問(wèn)意 “一口2.7.瓦7,7. 005 004. 001. 0C3, 00& 0C7. 0。6, 0Ooogoo00oogooooDO 3 8go o2.o o 6.o o6.o o
4、 3.15 8o o o o o o 7 7 70 15 7口物品的價(jià)格為:次選擇后, 次選擇后, 次選擇后, 次選擇后, 次選擇后,次選擇后 次選擇后, 次選擇后, 次選擇后,tni iT1政選擇后,價(jià)格為1次選擇后.價(jià)格為2次選擇后,偷格為價(jià)格為: 價(jià)格為: 林榕為C 疥格為: 價(jià)格為: 杯格為: 價(jià)格為; 彳介榕為; 彳介格為I2.宛g. ao16. 0020. 0028. 0085. 0039. 0047. 0053.00:60. 00t 6&. 00二 65. 00通過(guò)這次實(shí)驗(yàn),我回顧了貪心算法實(shí)現(xiàn)背包問(wèn)題,在其中加入了舍伍德隨機(jī)化過(guò)程得到物品的價(jià)格和重量,取值更加均勻,讓我熟悉了隨
5、機(jī)化算法, 使結(jié)果更可靠。貪心算法與動(dòng)態(tài)規(guī)劃有所不同, 貪心算法要求每一步的選擇都是當(dāng)前最優(yōu) 的解,剛開(kāi)始時(shí),我編寫(xiě)的代碼選擇的是選擇物品中價(jià)值最高的,后來(lái)發(fā)現(xiàn)忽實(shí)驗(yàn)心得視了重量,更改后每一步的最優(yōu)解應(yīng)該是選擇單位重量中價(jià)值最高的物品。另外由于需要改進(jìn)的地方:1,價(jià)重比排序中可以選擇其他的排序方法降低復(fù)雜度。.排序后輸出時(shí)可以將重量和價(jià)格同時(shí)輸出,即可減少一個(gè)循環(huán)。.對(duì)于隨機(jī)取數(shù)時(shí),出現(xiàn)重量為 0的情況不符合現(xiàn)實(shí),可以改進(jìn)。實(shí)驗(yàn)得分助教簽名附錄:完整代碼#include #include #include struct nodefloat value;float weight;float Va
6、lue,curvalue=0;float Weight,curweight=0;/按價(jià)重比冒泡排序void sort(node Node口,int M)int i,j;node temp;for(i=0;iM-1;i+)for(j=i+1;jM;j+)if(Nodei.value/(float)Nodei.weight)Nodej.value/(float)Nodej.weight)temp=Nodei;Nodei=Nodej;Nodej=temp;printf(物品的價(jià)重比從高到低依次排列為:n);for(i=0;iM;i+)printf(%.2f ,Nodei.value);printf(
7、n);for(i=0;iM;i+)printf(%.2f ,Nodei.weight);/裝包主要方法及輸出void pack(node Node,int M)int i,j=1;printf(nn選中物品的彳格為:n);for(i=0;iM;i+)if(Nodei.weight+curweight)=Weight)curvalue+=Nodei.value;curweight+=Nodei.weight;printf(第j次選擇為:j+;)int main()int i,M;printf(n請(qǐng)輸入背包容積:scanf(%f,&Weight);printf(n請(qǐng)輸入物品個(gè)數(shù):scanf(%d,&M);node NodeM;srand(time=NULL);for(
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年廣東省普通高等學(xué)校招收中等職業(yè)學(xué)校畢業(yè)生統(tǒng)一模擬考試語(yǔ)文題真題(解析版)
- 寒冷性脂膜炎的臨床護(hù)理
- 鼻竇壓痛的健康宣教
- 2021年工業(yè)機(jī)器人行業(yè)埃斯頓分析報(bào)告
- 汗孔角化病的臨床護(hù)理
- 聲音嘶啞的健康宣教
- 糖原貯積病Ⅱ型的臨床護(hù)理
- 《酒店禮儀知識(shí)培訓(xùn)》課件
- 黑色素沉著的臨床護(hù)理
- JJF(陜) 041-2020 寬帶采集回放系統(tǒng)校準(zhǔn)規(guī)范
- 【MOOC】創(chuàng)新與創(chuàng)業(yè)管理-南京師范大學(xué) 中國(guó)大學(xué)慕課MOOC答案
- 【MOOC】成本會(huì)計(jì)學(xué)-西北農(nóng)林科技大學(xué) 中國(guó)大學(xué)慕課MOOC答案
- 人教版道德與法治六上六年級(jí)道德與法治(上冊(cè))期末 測(cè)試卷(答案版)
- 2024年中國(guó)金蓮花膠囊市場(chǎng)調(diào)查研究報(bào)告
- 2024-2030年中國(guó)廢棄電器電子產(chǎn)品回收處理行業(yè)發(fā)展?fàn)顩r及投資規(guī)劃分析報(bào)告版
- 數(shù)據(jù)標(biāo)注合作合同模板
- 紀(jì)檢監(jiān)察干部實(shí)務(wù)培訓(xùn)
- 3.1《中國(guó)科學(xué)技術(shù)史序言(節(jié)選)》課件
- 旅游業(yè)VR體驗(yàn)館建設(shè)與管理計(jì)劃
- 2024-2025學(xué)年北師大版小學(xué)五年級(jí)上學(xué)期期末英語(yǔ)試題及答案指導(dǎo)
- 語(yǔ)文修辭-【專(zhuān)練02】 修辭手法考點(diǎn)專(zhuān)訓(xùn)(表達(dá)效果 主觀(guān)題1)(教師版)
評(píng)論
0/150
提交評(píng)論