資源描述:
《動態(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<