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

動態(tài)規(guī)劃求解資源分配實驗?zāi)繕?biāo)：（1）掌握用動態(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， Ci j為隨機產(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/C+等編程語言。實驗主要步驟：(1) 認(rèn)真閱讀實驗?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è)備后，可以為國家提供盈利Ci j(i臺設(shè)備提供給j號車間將得到的利潤，1in，1jm) 。問如何分配，才使國家得到最大的盈利？1. 問題分析：本問題是一簡單資源分配問題，由于具有明顯的最優(yōu)子結(jié)構(gòu)，故可以使用動態(tài)規(guī)劃求解，用狀態(tài)量fij表示用i臺設(shè)備分配給前j個車間的最大獲利，那么顯然有fij = max fkj1 + ci-kj ，0=k=i。再用pij表示獲得最優(yōu)解時第j號車間使用的設(shè)備數(shù)為i-pij，于是從結(jié)果倒推往回求即可得到分配方案。程序?qū)崿F(xiàn)時使用順推，先枚舉車間數(shù)，再枚舉設(shè)備數(shù)，再枚舉狀態(tài)轉(zhuǎn)移時用到的設(shè)備數(shù)，簡單3重for循環(huán)語句即可完成。時間復(fù)雜度為O(n2*m)，空間復(fù)雜度為O(n*m)，倘若此題只需求最大獲利而不必求方案，則狀態(tài)量可以減少一維，空間復(fù)雜度優(yōu)化為O(n)。程序代碼：#include#include#include#include#include#define N 31#define M 11int cNM, fNM, pNM;int main() int i, j, n, m, k; srand(time(NULL); n = 30; m = 10; for (int cas = 1; cas = 5; +cas) cout第cas個實例:endl; memset(c, 0, sizeof(c); for (i = 1; i = n; +i) for (j = 1; j = m; +j) cij = rand() % 1000; cout利潤表：endl; cout ; for (j = 1; j = m; +j) coutsetw(4)j; coutendl; for (i = 1; i = n; +i) coutsetw(4)i; for (j = 1; j = m; +j) coutsetw(4)cij; coutendl; memset(f, 0, sizeof(f); memset(p, -1, sizeof(p); for (j = 1; j = m; +j) for (i = 1; i = n; +i) for (k = 0; k = i; +k) if (fij fkj - 1 + ci - kj) fij = fkj - 1 + ci - kj; pij = k; cout最大獲利：fnmendl; cout資源分配匹配方案：= 1; -j) cout第j號車間使用k - pkj臺設(shè)備。endl; k = pkj; coutendl; return 0;實驗小結(jié)：