動(dòng)態(tài)規(guī)劃 求解資源分配 實(shí)驗(yàn)報(bào)告

ID:35426649

大?。?27.00 KB

頁(yè)數(shù):9頁(yè)

時(shí)間:2019-03-24

動(dòng)態(tài)規(guī)劃 求解資源分配 實(shí)驗(yàn)報(bào)告_第1頁(yè)
動(dòng)態(tài)規(guī)劃 求解資源分配 實(shí)驗(yàn)報(bào)告_第2頁(yè)
動(dòng)態(tài)規(guī)劃 求解資源分配 實(shí)驗(yàn)報(bào)告_第3頁(yè)
動(dòng)態(tài)規(guī)劃 求解資源分配 實(shí)驗(yàn)報(bào)告_第4頁(yè)
動(dòng)態(tài)規(guī)劃 求解資源分配 實(shí)驗(yàn)報(bào)告_第5頁(yè)
資源描述:

《動(dòng)態(tài)規(guī)劃 求解資源分配 實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

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

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

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

4、lude#include#include#include#include#defineN31#defineM11intc[N][M],f[N][M],p[N][M];intmain(){inti,j,n,m,k;srand(time(NULL));n=30;m=10;for(intcas=1;cas<=5;++cas){cout<<"第"<

5、=1;j<=m;++j)c[i][j]=rand()%1000;cout<<"利潤(rùn)表:"<

6、+k)if(f[i][j]=1;--j){cout<<"第"<

7、態(tài)規(guī)劃可得到一系列的解,求動(dòng)態(tài)規(guī)劃的基本步驟等都要有所理解。

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

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

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