动态规划实验报告.doc

数学计算机科学学院实验报告
专业名称：
物联网工程
实 验 室：
学苑楼6幢301室
实验课程：
算法设计与分析实验
实验名称：
动态规划
姓 名：
李存凤
学 号：
120706019
同组人员：
实验日期：
2014-5-7
一、实验目的
熟练掌握动态规划思想及教材中相关经典算法。
掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。
二、实验仪器
1、计算机
三、实验原理
1、动态规划是求解最优化问题的算法设计，分布决策。
四、实验内容与步骤
(i）找零钱问题
«问题描述
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=
∞。
«编程任务
设计一个动态规划算法，对1≤j≤L，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性
«数据输入
数据的第1行中有1个正整数n（n<=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。
（1）建立环境工程，编写程序如下：
#include<>
int n,L; //n种硬币L长的数组
int c[13][20];
int T[13];//硬币面值
int jisuan(int i,int j);
int main()
{
int k;
printf("请输入硬币种数：");
scanf("%d",&n);
printf("请输入面值数：");
for(int i=1;i<=n;i++)
scanf("%d",&T[i]);
printf("请输入长度：");
scanf("%d",&L);
k=jisuan(n,L);
printf("请输出硬币个数：");
printf("%d",k);
return 0;
}
int jisuan(int i,int j)
{
int min;
if((i==0)||(j==0))
c[i][j]=0;
if(i==1)
{
if(((1<=j)&&(j<T[1]))||((T[1]<=j)&&(j<=L)&&(j%T[1]!=0)))
c[i][j]=500;
if((T[i]<=j)&&(j<=L)&&(j%T[i]==0))
c[i][j]=j/T[i];
}
else
{
min=jisuan(i-1,j);
for(int x=j/T[i];x>0;x--)
{
int a=jisuan(i-1,j-x*T[i])+x;
if(min>a)
min=a;
}
c[i][j]=min;
}
return c[i][j];
}
石子合并问题
«问题描述
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
«编程任务
编写程序，计算出将n堆石子合并成一堆的最小得分。
«数据输入
第1 行是正整数n（1<=n<=100），表示有n堆石子。
第2行有n个数，分别表示每堆石子的个数。
建立环境工程，编写程序如下：
#include<>
int n,i;
int num[10];
int re(int i, int j);
int Sum(int i,int j);
void recyle();
void main()
{
int min;
printf("请输入石子堆数：");
scanf("%d", &n);
printf("请输入每堆石子个数：");
for ( i = 1; i <=n; i++)
scanf("%d", &num[i]);
min = re(1, n);
for (int i = 0; i < n - 1; i++)
{
recyle();
if (re(1, n) < min)
min = re(1, n);
}
printf("%d", min);
}
int re(int i,int j)
{
int min;
if (j == 1)
return 0;
i