動態(tài)規(guī)劃_求解資源分配_實驗報告

ID:26853188

大?。?30.05 KB

頁數(shù):8頁

時間:2018-11-29

動態(tài)規(guī)劃_求解資源分配_實驗報告_第1頁
動態(tài)規(guī)劃_求解資源分配_實驗報告_第2頁
動態(tài)規(guī)劃_求解資源分配_實驗報告_第3頁
動態(tài)規(guī)劃_求解資源分配_實驗報告_第4頁
動態(tài)規(guī)劃_求解資源分配_實驗報告_第5頁
資源描述:

《動態(tài)規(guī)劃_求解資源分配_實驗報告》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫

1、動態(tài)規(guī)劃求解資源分配姓名:白云志班級:計算機1103學(xué)號:1111610427實驗?zāi)繕耍海?)掌握用動態(tài)規(guī)劃方法求解實際問題的基本思路。(2)進一步理解動態(tài)規(guī)劃方法的實質(zhì),鞏固設(shè)計動態(tài)規(guī)劃算法的基本步驟。實驗任務(wù):(1)設(shè)計動態(tài)規(guī)劃算法求解資源分配問題,給出算法的非形式描述。(2)在Windows環(huán)境下用C語言實現(xiàn)該算法。計算10個實例,每個實例中n=30,m=10,Cij為隨機產(chǎn)生于范圍(0,103)內(nèi)的整數(shù)。記錄各實例的數(shù)據(jù)及執(zhí)行結(jié)果(即最優(yōu)分配方案、最優(yōu)分配方案的值)、運行時間。(3)從理論上分析算法的時間和空間復(fù)雜度,并由此解釋相應(yīng)的實驗結(jié)果。實驗設(shè)備及環(huán)境:PC;C/

2、C++等編程語言。實驗主要步驟:(1)認真閱讀實驗?zāi)康呐c實驗任務(wù),明確本次實驗的內(nèi)容;(2)分析實驗中要求求解的問題,根據(jù)動態(tài)規(guī)劃的思想,得出優(yōu)化方程;(3)從問題出發(fā),設(shè)計出相應(yīng)的動態(tài)規(guī)劃算法,并根據(jù)設(shè)計編寫程序?qū)崿F(xiàn)算法;(4)設(shè)計實驗數(shù)據(jù)并運行程序、記錄運行的結(jié)果;(5)分析算法的時間和空間復(fù)雜度,并由此解釋釋相應(yīng)的實驗結(jié)果;問題描述:資源分配問題某廠根據(jù)計劃安排,擬將n臺相同的設(shè)備分配給m個車間,各車間獲得這種設(shè)備后,可以為國家提供盈利Cij(i臺設(shè)備提供給j號車間將得到的利潤,1≤i≤n,1≤j≤m)。問如何分配,才使國家得到最大的盈利?1.問題分析:本問題是一簡單資源

3、分配問題,由于具有明顯的最優(yōu)子結(jié)構(gòu),故可以使用動態(tài)規(guī)劃求解,用狀態(tài)量f[i][j]表示用i臺設(shè)備分配給前j個車間的最大獲利,那么顯然有f[i][j]=max{f[k][j–1]+c[i-k][j]},0<=k<=i。再用p[i][j]表示獲得最優(yōu)解時第j號車間使用的設(shè)備數(shù)為i-p[i][j],于是從結(jié)果倒推往回求即可得到分配方案。程序?qū)崿F(xiàn)時使用順推,先枚舉車間數(shù),再枚舉設(shè)備數(shù),再枚舉狀態(tài)轉(zhuǎn)移時用到的設(shè)備數(shù),簡單3重for循環(huán)語句即可完成。時間復(fù)雜度為O(n^2*m),空間復(fù)雜度為O(n*m),倘若此題只需求最大獲利而不必求方案,則狀態(tài)量可以減少一維,空間復(fù)雜度優(yōu)化為O(n)。程

4、序代碼:#include#includeusingnamespacestd;classFruit//定義一個類,名字叫Fruit{stringname;//定義一個name成員stringcolour;//定義一個colour成員public:friendistream&operator>>(istream&,Fruit&);//必須要聲明為友元啊,不然怎么輸入啊friendostream&operator<<(ostream&,constFruit&);//同理voidprint()//定義一個輸出名字的成員print(){cout<

5、lour<<""<>(istream&in,Fruit&s)//我是輸入操作符的重載{in>>s.colour>>s.name;if(!in)c

6、err<<"Wronginput!"<>apple;cout<

當前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭