用貪心算法求解背包問題_第1頁
用貪心算法求解背包問題_第2頁
用貪心算法求解背包問題_第3頁
用貪心算法求解背包問題_第4頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

《算法設計與分析》實驗題目實驗時間一、實驗目的及要求1.理解貪心算法的概念2.掌握貪心算法的要素1）最優(yōu)子結構性質(zhì)2）貪心選擇性質(zhì)3.理解貪心算法與動態(tài)規(guī)劃算法的差異4.理解貪心算法的一般理論5.通過一些應用范例學習貪心設計策略二、實驗內(nèi)容、過程和結果（實驗主要內(nèi)容的介紹、主要的操作步驟、程序代碼和測試數(shù)據(jù)及實驗結果）1.實驗內(nèi)容介紹：背包問題：背包問題與0-1背包問題類似，所不同的那是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定是全部裝入背包。用貪心算法解背包問題的基本步驟是，首先計算每種物品單位重量的價值 ui/wi;然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依次策略一直進行下去，知道背包裝滿為止。1/42.程序代碼：#include<iostream.h>voidsort(intn,floatv[],floatw[]);voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){sort(n,v,w);for(inti=0;i<n;i++)x[i]=0;floatc=M;for(i=0;i<n;i++)cout<<w[i]<<endl;for(i=0;i<n;i++){if(w[i]>c) break;x[i]=1;c=c-w[i];}if(i<n){x[i]=c/w[i];}}用貪心算法求解背包問題voidsort(intn,floatv[],floatw[])2/4{float*p=newfloat[n];for(inti=0;i<n;i++){p[i]=v[i]/w[i];cout<<p[i]<<endl;}//floattemp;floattempw;for(i=0;i<=n-2;i++){for(intj=i+1;j<n;j++){if(p[i]<p[j]){tempw=w[j];w[j]=w[i];w[i]=tempw;}}}}voidmain(){intn=5;3/4floatM=10;floatv[]={5,3,4,1,2};floatw[]={1,3,2,4,5};float x[5];intj=0;Knapsack(n,M,v,w,x);for(j=0;j<n;j++)co

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論