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