第一篇：實驗報告：動態規劃01背包問題)范文
XXXX
大 學 計 算 機 學 院 實 驗 報 告
計算機學院
2017
級
軟件工程
專業
班
指導教師
學號
姓名
2019
年 10
月 21
日
成績
課程名稱 算法分析與設計 實驗名稱 動態規劃---0-1 背包問題①理解遞歸算法的概念
實驗目的②通過模仿 0-1 背包問題，了解算法的思想③練習0-1 背包問題算法
實驗儀器 電腦、jdk、eclipse 和器材
實驗：
0-1 背包算法：給定
N 種物品，每種物品都有對應的重量
weight 和價值 value，一個容
量為 maxWeight 的背包，問：應該如何選擇裝入背包的物品，使得裝入背包的物品的總價值
最大。（面對每個物品，我們只有拿或者不拿兩種選擇，不能選擇裝入物品的某一部分，也 實
驗 不能把同一個物品裝入多次）代碼如下所示：
內 public class
KnapsackProblem {
容 /**
、上 * @paramweight 物品重量
機 * @paramvalue 物品價值 調 * @parammaxweight
背包最大重量
試
程 *
@return maxvalue[i][j] 中，i 表示的是前 i 個物品數量，j 表示的是重量
序 */
、public
static
int knapsack（int
[]
weight , int
[]
value , int
maxweight){
程
序
運
行
結
果
實
驗
內 int
n =;
包問題的算法思想：將前 i 個物品放入容量 容 為 w 的背包中的最大價值。有如下兩種情況：、①若當前物品的重量小于當前可放入的重量，便可考慮是 上 否要將本件物品放入背包中或者將背包中的某些物品拿出 機 來再將當前物品放進去；放進去前需要比較（不放這個物 調 品的價值）和（這個物品的價值放進去加上當前能放的總 試 重量減去當前物品重量時取
i-1 個物品是的對應重量時候 程 的最高價值），如果超過之前的價值，可以直接放進去，反 序 之不放。
、②若當前物品的重量大于當前可放入的重量，則不放入 程 背包問題利用動態規劃的思路可以這樣理解：階段是“物 序 品的件數”，狀態就是“背包剩下的容量”，f[i,v]
表示設 運 從前 i 件物品中選擇放入容量為 V 的背包的最大價值。那 行 么狀態轉移的方法為
:
結
f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}
果
這個方程可以理解為：只考慮子問題“將前 i 個物品放入
容量為 v的背包中的最大價值” 那么可以考慮不放入
i，最
大價值就和 i
無關，就是 f[i-1][v], 如果放入第i
個物品，價值就是 f[i-1][v-w[i]]+value[i], 只取最大值即可。
實
驗
內
容、上
機
調
試
程
序、程
序
運
行
結
果
第二篇：用動態規劃的思想實現動態投資問題 實驗報告
算法實驗報告二 動態規劃法
一、實驗目的：用動態規劃的思想實現動態投資問題。
二、實驗要求：掌握動態規劃算法設計的基本策略。
三、實驗內容：m元錢，n項投資，fi(x)將x元投入第i項項目的效益，目標函數max {f1(x1)+ f2(x2)+ … + fn(xn)}
約束條件x1 + x2 + … + xn = m，xi ∈ N
設Fk(x)表示x元錢投給前k個項目的最大效益 算法實現：投資第k個項目p元錢的效益可表示為Project[k][p],其中0<=k<=n,0<=p<=m;設投資給前k個項目p元 錢的最終總效益為用Benefit[k][p]，其中0<=k<=n,0<=p<=m。設allot[k][p]表示在總投資為p元錢時候，最終分配給第k個項目的錢數解。
四、實驗心得：在調試過程中出現了好多小問題，一開始結果不對，我通過單步調試一步步的看待填的二維表中的數據。發現大部分V[i][j]對了，但是有極小數的不對。故而我的結果出現了問題。通過本次實驗加深了我對動態規劃算法的理解。而且對動態規范編寫代碼解決一個實際問題有了進一步的認識。即當算法考慮的原問題的每一個子問題，算法都需要計算一個最優解。換句話說，所有算法生成的表項表示算法考慮的子問題的最優解。這時候用動態規范把每一個最優解求出來（利用遞歸公式），就能夠保證最后求得的一定是最優解。而且動態規劃有個特點，即它是由底向上，它實現起來就是利用循環，有時用到一層循環即可，有時要用到兩層for循環即可以求解出問題。
五：附錄：程序代碼及結果
#include
void main(){
void jie(int,int,int d[][9]);
void Invest(int m,int n,int f[][9],int g[][9],int d[][9]);
int m=8,n=3,f[4][9],d[4][9];int
g[4][9]={{0},{0,5,15,40,80,90,95,98,100},{0,5,15,40,60,70,73,74,75},{0,4,26,40,45,50,51,53,53}};
Invest(m,n,f,g,d);
printf(“可獲得的最大收益為：%dn”,f[3][8]);
jie(m,n,d);} void Invest(int m,int n,int f[][9],int g[][9],int d[][9]){ int i,j,k,s;for(j=0;j<=m;j++)
{
f[1][j]=g[1][j];d[1][j]=j;}
for(i=2;i<=n;i++)
for(j=0;j<=m;j++)
{
f[i][j]=0;
for(k=0;k<=j;k++)
{
s=f[i-1][j-k]+g[i][k];
if(s>f[i][j])
{
f[i][j]=s;d[i][j]=k;}
}
}
} void jie(int m,int n,int d[][9]){ int s=m;int k[4];int i;k[n]=d[n][m];for(i=n-1;i>0;i--){
s = s-k[i+1];
k[i] = d[i][s];} for(i=1;i<=3;i++)
} printf(“%5d”,k[i]);printf(“n”);
第三篇：c語言版背包問題
#include
int c[10][100];/*對應每種情況的最大價值*/
int knapsack(int m,int n){
int i,j,w[10],p[10];
printf(“請輸入每個物品的重量,價值：n”);
for(i=1;i<=n;i++)
scanf(“%d,%d”,&w[i],&p[i]);
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化數組*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(w[i]<=j)/*如果當前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
/*如果本物品的價值加上背包剩下的空間能放的物品的價值*/
/*大于上一次選擇的最佳方案則更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main(){
int m,n;int i,j;
printf(“請輸入背包的承重量,物品的總個數：n”);
scanf(“%d,%d”,&m,&n);
printf(“旅行者背包能裝的最大總價值為%d”,knapsack(m,n));
printf(“n”);
return 0;}
第四篇：動態路由配置實驗報告
實驗名稱：姓
名：專
業：班
級：學
號：指導教師：實驗日期：
動態路由的配置
江西理工大學南昌校區
實驗報告
【實驗目的】
1.學會用配置靜態路由； 2.學會用RIP協議配置動態路由。
【實驗原理】
動態路由是網絡中的路由器之間相互通信，傳遞路由信息，利用收到的路由信息更新路由器表的過程。它能實時地適應網絡結構的變化。如果路由更新信息表明發生了網絡變化，路由選擇軟件就會重新計算路由，并發出新的路由更新信息。這些信息通過各個網絡，引起各路由器重新啟動其路由算法，并更新各自的路由表以動態地反映網絡拓撲變化。動態路由適用于網絡規模大、網絡拓撲復雜的網絡。
RIP采用距離向量算法，即路由器根據距離選擇路由，所以也稱為距離向量協議。路由器收集所有可到達目的地的不同路徑，并且保存有關到達每個目的地的最少站點數的路徑信息，除到達目的地的最佳路徑外，任何其它信息均予以丟棄。同時路由器也把所收集的路由信息用RIP協議通知相鄰的其它路由器。這樣，正確的路由信息逐漸擴散到了全網。
【實驗步驟】
1.在Packet Tracer軟件環境當中搭建實驗環境，并畫出如下拓撲圖，共使用4臺路由器，5臺PC機，1臺交換機，其中兩個路由器之間用交叉線連接，交換機與其他設備都用直通線連接。
圖一 網絡拓撲圖
江西理工大學南昌校區
實驗報告
2.按照事先想好的如上圖中標示的地址在計算機中設置好IP地址，子網掩碼，默認網關。如設置PC1的相關截圖如下：
圖二 PC1的IP地址
圖三 PC1的網關
3．利用ping命令測試同一網段的兩臺PC機之間的連通性，若出現Reply from語句則表示兩臺PC機之間相互連通了，若出現Request timed out則表示還沒有連 3 江西理工大學南昌校區
實驗報告
通，如下圖所示是測試同一網段的PC0和PC4之間的連通性，出現Reply from語句，表示兩臺計算機之間連通了。
圖四 用ping命令測試連通性
4.在路由器中分別添加與之相連的網段的網絡號，相關截圖如下：
圖五 路由器設置
5.利用ping命令測試不同網段的PC機（PC1和PC3）之間的連通性，測試結果如下，結果表明連通了。江西理工大學南昌校區
實驗報告
圖六 用ping命令測試連通性
【實驗總結】
經過第一次實驗的鍛煉，此時實驗簡單了很多。在課上老師講的很詳細，我們跟著老師的步驟操作，比較輕松的就完成了此次實驗，在實驗中熟練掌握動態路由協議RIP及RIP路由協議的配置方法、熟悉配置RIP路由表項的基本操作步驟、掌握在小型規模網絡中配置實現RIP距離矢量類路由協議的方法等。通過此次試驗感覺學到了不少東西，收獲感很強。
第五篇：動態規劃教案
吉林師范大學計算機學院
教
案
課 程 名 稱 院系
級
C 程序設計(算法部分)
計算機學院計算機科學與技術09級
教研室(系、實驗室)計算機基礎教研室5101 授 課 班 級 09計算機科學與技術3班 實習
生
鄭言
系指導教師
滕國文
吉林師范大學計算機學院
二○一二年四月二十五日（星期三5，6節）
課型章節：
動態規劃基本思想
基要本參教考材資和料主：
算法設計與分析》 教學目的：
本課程以C語言為教授程序設計的描述語言，結合語言介紹程序設計的基本原理、技巧和方法。主要講授內容包括程序設計動態規劃基本概念，動態規劃的基本步驟，動態規劃問題的特征。通過本課程的學習，為算法更好的學習，以及能用計算機解決一些實際問題打下堅實的基礎。教學基本要求：
掌握C語言中動態規劃的基本概念，動態規劃的基本步驟，動態規劃問題的特征。并能熟練使用C語言動態規劃思想解決一些簡單程序問題；掌握一些基本算法結構及相關方法；熟悉程序設計的思想和編程技巧。重點：
動態規劃基本概念，動態規劃的基本步驟，動態規劃問題的特征。難點: 動態規劃的基本步驟 課型：
理論課 教法：
1.多媒體講解 2.舉例講解 教學內容及過程： 1.課前回顧：
枚舉法: 在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結論，那么這結論是可靠的，這種歸納方法叫做枚舉法．
2.數塔問題
有形如下圖所示的數塔，從頂部出發，在每一結點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。簡單的進行選舉方法的引導，讓同學們主動思考到動態規劃的思想上了?？紤]一下：
從頂點出發時到底向左走還是向右走應取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。
同樣，下一層的走向又要取決于再下一層上的最大值是否已經求出才能決策。這樣一層一層推下去，直到倒數第二層時就非常明了。
如數字2，只要選擇它下面較大值的結點19前進就可以了。所以實際求解時，可從底層開始，層層遞進，最后得到最大值。
結論：自頂向下的分析，自底向上的計算。#include
return x;else
return y;} main(){ int a[100][100];int i,j,n;scanf(“%d”,&n);for(i=0;i for(j=0;j<=i;j++) scanf(“%d”,&a[i][j]);for(i=n-2;i>=0;i--) for(j=0;j<=i;j++) { a[i][j]+=max(a[i+1][j],a[i+1][j+1]); } printf(“%dn”,a[0][0]);} 3.總結“動態規劃的基本思想” 如果各個子問題不是獨立的，不同的子問題的個數只是多項式量級，如果我們能夠保存已經解決的子問題的答案，而在需要的時候再找出已求得的答案，這樣就可以避免大量的重復計算。由此而來的基本思路是，用一個表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計算過，就將其結果填入表中。 4.總結“動態規劃的基本步驟” 動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值（最大值或最小值）的那個解。設計一個動態規劃算法，通?？梢园匆韵聨讉€步驟進行： （1）找出最優解的性質，并刻畫其結構特征。（2）遞歸地定義最優值。 （3）以自底向上的方式計算出最優值。 （4）根據計算最優值時得到的信息，構造一個最優解。 其中（1）——（3）步是動態規劃算法的基本步驟。在只需要求出最優值的情形，步驟（4）可以省去。若需要求出問題的一個最優解，則必須執行步驟（4）。此時，在步驟（3）中計算最優值時，通常需記錄更多的信息，以便在步驟（4）中，根據所記錄的信息，快速構造出一個最優解。 5.總結“動態規劃問題的特征” 動態規劃算法的有效性依賴于問題本身所具有的兩個重要性質： 1、最優子結構：當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。 2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。6.思考： 《免費餡餅》 題目描述: 都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內。餡餅如果掉在了地上當然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側都不能站人，所以他只能在小徑上接。由于gameboy平時老呆在房間里玩游戲，雖然在游戲中是個身手敏捷的高手，但在現實中運動神經特別遲鈍，每秒種只有在移動不超過一米的范圍內接住墜落的餡餅?，F在給這條小徑如圖標上坐標： 為了使問題簡化，假設在接下來的一段時間里，餡餅都掉落在0-10這11個位置。開始時gameboy站在5這個位置，因此在第一秒，他只能接到4,5,6這三個位置中期中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（假設他的背包可以容納無窮多個餡餅） #include 7.課后作業 杭電ACM 1003、1466、1087、1159、1176、1058、1069、2059、2084
點擊咨詢 