算法设计与分析-动态规划算法的应用——沐雨先生

一、实验目的

1． 掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。

2．熟练掌握分阶段的和递推的最优子结构分析方法。

3． 学会利用动态规划算法解决实际问题 。

二、实验内容

1. 问题描述 ：数据输入可个人设定，由键盘输入。（下述题目请在上机前完成程序代码的准备，之后在机房完成撰写代码、结果截图及实验报告提交），

题目一：数塔问题
给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。
输入样例（数塔）：
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
输出样例（最大路径和）：
59

题目二 0-1 背包问题
给定 n 种物品和一个背包。物品 i 的重量是 wi ，其价值为 vi ，背包的容量为 c 。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大 ? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量 c ，物品的个数 n 。接下来的 n 行表示 n 个物品的重量和价值。输出为最大的总价值。
输入样例：
20 3
11 9
9 10
7 5
输出样例
19

源程序

题目一

#include<stdio.h>
int main(){int a[50][50][3];int n,i,j;printf("请输入三角形行数：");while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=i;j++){scanf("%d",&a[i][j][1]);a[i][j][2]=a[i][j][1];a[i][j][3]=0;}for(i=n-1;i>=1;i--)for(j=1;j<=i;j++){if(a[i+1][j][2]>a[i+1][j+1][2]){a[i][j][2]+=a[i+1][j][2];a[i][j][3]=0;}else {a[i][j][2]+=a[i+1][j+1][2];a[i][j][3]=1;}}printf("最大路径之和为：%d\n",a[1][1][2]);printf("路径为:\n");j=1;for(i=1;i<n;i++){printf("%d->",a[i][j][1]);j+=a[i][j][3];}printf("%d\n",a[i][j][1]);}
}

题目二

#include<stdio.h>
#include<stdlib.h>int V[100][100];//前i个物品装入容量为j的背包中获得的最大价值int max(int a,int b){if(a>=b)return a;else return b;
}int KnapSack(int n,int weight[],int value[],int C){int i;//填表,其中第一行和第一列全为0,即 V(i,0)=V(0,j)=0； for(i=0;i<=n;i++)V[i][0]=0;for(int j=0;j<=C;j++)V[0][j]=0;//用到的矩阵部分V[n][C] ,下面输出中并不输出 第1行和第1列 //	printf("编号 重量 价值  ");  //菜单栏 1 
//	for(i=1;i<=C;i++)
//		printf(" %2d ",i);
//	printf("\n\n");for(i=1;i<=n;i++){
//		printf("%2d   %2d   %2d     ",i,weight[i-1],value[i-1]);  //菜单栏 2 (weight与value都是从0开始存的，所以开始i=1时对应0的位置)for(int j=1;j<=C;j++){if(j<weight[i-1]){  //包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的V[i][j]=V[i-1][j];
//				printf("%2d  ",V[i][j]);}else{  //还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个V[i][j]=max(V[i-1][j],V[i-1][j-weight[i-1]]+value[i-1]);		
//				printf("%2d  ",V[i][j]);}}
//		printf("\n");}return V[n][C];}void Judge(int C,int n,int weight[]){	//判断哪些物品被选中		int j=C,i;int *state=(int *)malloc(n*sizeof(int));for(i=n;i>=1;i--){if(V[i][j]>V[i-1][j]){  //如果装了就标记，然后减去相应容量 state[i]=1;j=j-weight[i-1];}elsestate[i]=0;}printf("选中的物品是:");for(i=1;i<=n;i++)if(state[i]==1)printf("%d ",i);printf("\n");
}int main(){int n,i;        //物品数量 int Capacity;//背包最大容量printf("请输入背包的最大容量:");scanf("%d",&Capacity);printf("输入物品数:");scanf("%d",&n);int *weight=(int *)malloc(n*sizeof(int));//物品的重量int *value=(int *)malloc(n*sizeof(int)); //物品的价值printf("请输入物品相应的的重量和价值:\n");for(i=0;i<n;i++)scanf("%d %d",&weight[i],&value[i]);int s=KnapSack(n,weight,value,Capacity);  //获得的最大价值Judge(Capacity,n,weight);  //判断那些物品被选择 printf("最大物品价值为: ");printf("%d\n",s);return 0;
}