一、实验目的
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];
}
else
state[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;
}
