文档介绍：数学计算机科学学院实验报告
专业名称：物联网工程实验室：一学苑楼6幢301室实验课程：算法设计与分析实验
实验名称：动态规划
姓名：李存风
学号： 120706019
同组人员：
实验日期： 2014-5-7
数学计算机科学学院实验报告
专业名称：物联网工程实验室：一学苑楼6幢301室实验课程：算法设计与分析实验
实验名称：动态规划
姓名：李存风
学号： 120706019
同组人员：
实验日期： 2014-5-7
一、实验目的
(1) 熟练掌握动态规划思想及教材中相关经典算法。
(2) 掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。
二、实验仪器
1、计算机三、实验原理
1、动态规划是求解最优化问题的算法设计，分布决策。
四、实验内容与步骤
(i)找零钱问题
★问题描述
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数 j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=8。
★编程任务
设计一个动态规划算法，对 1 w j W 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-1j);
for(int x=j/T[i];x>0;x--)
{
int a=jisuan(i-1J-x*T[i])+x;
if(min>a)
min=a;
}
c[i][j]=min;
return c[i][j];
(ii)石子合并问题