第一篇：实验报告：动态规划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平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标： 为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼） #include 7.课后作业 杭电ACM 1003、1466、1087、1159、1176、1058、1069、2059、2084
点击咨询 