淮海工學院計算機工程學院
實驗報告書
課程名： 《演算法分析與設計》
題目： 實驗2 動態規劃演算法
最大子段和問題
班級軟體081班
學號110831116
姓名陳點點
實驗2 動態規劃演算法
實驗目的和要求
（1）深刻掌握動態規劃法的設計思想並能熟練運用；
（2）理解這樣乙個觀點：同樣的問題可以用不同的方法解決，乙個好的演算法是反覆努力和重新修正的結果。
（3）分別用蠻力法、分治法和動態規劃法設計最大子段和問題的演算法；
（4）比較不同演算法的時間效能；
（5）給出測試資料，寫出程式文件
實驗內容
給定由n個整數組成的序列(a1, a2, …, an)，求該序列形如的子段和的最大值，當所有整數均為負整數時，其最大子段和為0。
實驗環境
turbo c 或vc++
實驗學時
2學時，必做實驗
資料結構與演算法
資料結構: 程式中所用的資料都是儲存在陣列當中
演算法: 蠻力法函式maxsum(int a,int n,int &besti,int &bestj)
分治法函式maxsum(int a,int left,int right)
動態規劃法函式 maxsum(int n,int a)
核心源**
1， 蠻力法
t(n)=o(n2)。
#include
int maxsum(int a,int n,int &besti,int &bestj)
}return sum;
}void main()
2，分治法
t(n)=o(nlog(n))。
#include
int maxsum(int a,int left,int right)
else
void main()
3，動態規劃法
t(n)=o(n)。
#include
void maxsum(int n,int a)
cout<<"整數序列的最大子段和是："< }
void main()
實驗結果
1，蠻力法：
2，分治法：
3，動態規劃法：
實驗體會
同樣的問題可以用不同的方法解決，乙個好的演算法是反覆努力和重新修正的結果。雖然蠻力法，分治法，動態規劃法都可以解決最大子段和這個問題，但是這些方法的時間複雜度各不相同，時間複雜度越低，代表這個方法更優越。通過這次實驗，我對動態規劃法有了深刻的理解，同時也對前面所學的蠻力法和分治法進行了複習，體會到演算法設計技術的思想方法。
動態規劃法解
2011級3班張思源 動態規劃演算法原理 將待求解的問題分解成若干個相互聯絡的子問題，先求解子問題，然後從這些子問題的解得到原問題的解 對於重複出現的子問題，只在第一次遇到的時候對它進行求解，並把答案儲存起來。為了不去求解相同的子問題，引入乙個陣列，把所有子問題的解存於該陣列中，這就是動態規劃所採用...
揹包問題的動態規劃法
揹包問題 在m件物品取出若干件放在空間為w的揹包裡，每件物品的重量為w1，w 2 wn，與之相對應的價值為p1,p2 pn。求出獲得最大價值的方案。注意 在本題中，所有的重量值均為整數。演算法分析 對於揹包問題，通常的處理方法是搜尋。用遞迴來完成搜尋，演算法設計如下 function make i ...
備忘錄方法 動態規劃法的變形
求lcs的問題。當xi yj時，求c i,j 只需知道c i 1,j 1 而無需用到c i,0 c i,j 1 及c i 1,j c i 1,n 當只需求出乙個lcs時，可能有一些c p,q 在整個求解過程中都不會用到。一般地，當某個問題可以用動態規劃法求解,但二維陣列中有相當一部分元素在整個計算中...