實驗報告
實驗內容
姓名： 魏成林
學號： 201101020126
班級： 電腦科學與技術
完成日期： 2013-11-7
實驗要求
一、實驗目的
1. 了解動態規劃和貪心選擇演算法
2. 區分兩個演算法
二、實驗內容
1. 實現矩陣連乘、0-1揹包問題、最優搜尋樹三個問題的動態規劃演算法。
2．實現活動安排的貪心演算法。
3. 對動態規劃和貪心演算法進行比較。
實驗報告
一 、實驗問題回答
1. 概述動態規劃演算法思想。
答：將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。儲存已解決的子問題的答案，在需要的時候再找出來避免重複計算，從而得到演算法。
2. 滿足什麼條件的問題可以用動態規劃演算法求解。
答：具有最優子結構和子問題重疊性質。
3. 寫出動態規劃演算法求解的步驟。
答：(1)找出最優解的性質，並刻畫其結構特徵；
(2)遞迴的定義最優值；
(3)以自底向上的方式計算出最優值；
(4)根據計算最優值時得到的資訊，構造最優解。
4. 什麼是最優子結構，如何證明乙個問題有最優子結構性質。
答：問題的最優解包含著其子問題的最優解；利用反證法來證明乙個問題有最優子結構性質，假設乙個問題不具有最優子結構性質，然後逐步的證明該問題存在最優子結構性質，與假設的產生矛盾，假設不成立，所以該問題就有最優子結構。
5. 寫出貪心演算法思想。
答：貪心演算法並不從整體最優考慮，而是作出在某種區域性意義上的最優選擇。
6. 貪心演算法的基本要素是什麼？
答：具有最優子結構性質和貪心選擇性質。
7. 0-1揹包問題可否用貪心演算法求解？不可以是為什麼？如果可以請用貪心演算法實現，並與動態規劃演算法實現的0-1揹包問題求解結果對比，是否正確。
答：0-1揹包問題不能用貪心演算法求解。因為在某種情況下，不能保證揹包被裝滿，也就是說揹包有剩餘的空間沒有利用起來，導致無法達到最大價值。
8. 分治策略和動態規劃的異同。
答：分治策略得到的子問題往往是獨立的，而動態規劃得到的子問題不是獨立的。分治法得到的子問題太多導致耗費時間，而且存在許多的重複計算。動態規劃則可以避免重複計算。
9. 動態規劃和貪心選擇的異同。
答：共同點是兩種演算法都需要問題具有最優子結構。不同的是有些問題可以用貪心演算法求解，而有些問題不能用貪心演算法求解。
二、實驗總結與收穫
用幾句簡短的話對實驗進行總結，並寫出自己的心得和收穫。每一項都用幾個小點表示。如：
本次實驗收穫如下：
1. 。。。。。。
2. 。。。。。。
實驗5動態規劃實驗
曹加站 20111060255 資訊計科 1.實驗目的要求 把動態規劃演算法應用到求貨郎擔問題和矩陣乘法問題，並程式設計實現。2.實驗主要內容 1 寫出並除錯用動態規劃方法求中點座標程式。2 寫出並除錯用動態規劃方法求矩陣乘法的程式。下面是矩陣連乘問題的動態規劃演算法 假設有6個矩陣 a1 a2 a...
實驗七動態規劃求解揹包問題
實驗目的 1 以0 1揹包問題為例，掌握動態規劃演算法的基本設計策略 2 掌握並實現求解0 1揹包問題的動態規劃演算法 3 分析實驗結果。實驗環境 計算機 c語言程式設計環境 實驗學時 2學時實驗內容與步驟 1.理解0 1揹包問題 0 1揹包問題的描述 已知有n個物品和乙個承重為m的揹包，物品i的重...
動態規劃練習題及解答
題1 多公尺諾骨牌 domino 問題描述 有一種多公尺諾骨牌是平面的，其正面被分成上下兩部分，每一部分的表面或者為空，或者被標上1至6個點。現有一行排列在桌面上 頂行骨牌的點數之和為6 1 1 1 9 底行骨牌點數之和為1 5 3 2 11。頂行和底行的差值是2。這個差值是兩行點數之和的差的絕對值...