{
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];
指导教师签名
时间
年
月
日
min = a;
else
min = b;
}
return min;
}
int Sum(int i, int j)
{
int sum=0;
for (int m = 1; m <= j; m++)
sum += num[m];
return sum;
}
void recyle()
{
int m;
num[0] = num[1];
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)
二、实验仪器
1、计算机
三、实验原理
1、动态规划是求解最优化问题的算法设计，分布决策。
四、实验内容与步骤
(i）找零钱问题
问题描述
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=∞。
if (j == 2)
{
min = num[i] + num[i+1];
}
if (j>2)
{
int sum = Sum(i, j);
int a = re(i, j-1) + re(i+j-1,1)+sum;
int b = re(i, 1) + re(i+1, j - 1) + sum;
if (a <= b)
编程任务
编写程序，计算出将n堆石子合并成一堆的最小得分。
数据输入
第1 行是正整数n（1<=n<=100），表示有n堆石子。
第2行有n个数，分别表示每堆石子的个数。
建立环境工程，编写程序如下：
#include<stdio.h>
int n,i;
int num[10];
int re(int i, int j);
数学计算机科学学院实验报告
专业名称：
物联网工程
实 验 室：
学苑楼6幢301室
实验课程：
算法设计与分析实验
实验名称：
动态规划
姓 名：
李存凤
学 号：
120706019
同组人员：
实验日期：
2014-5-7
一、实验目的
（1）熟练掌握动态规划思想及教材中相关经典算法。
（2）掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。
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;
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]);
for (m = 2; m <=n; m++)
num[m - 1] = num[m];
num[n] = num[0];
}
五、实验结果和分析
1、找零钱问题问题程序运行结果如下：
2、石子合并问题程序运行结果如下：
成绩评定
1、根据实验情况和实验报告质量作出写实性评价
2、评分
综合评分
折合成等级
优秀 良好 中等 差
编程任务
设计一个动态规划算法，对1≤j≤L，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性
数据输入
数据的第1行中有1个正整数n（n<=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。
（1）建立环境工程，编写程序如下：
}
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];
}
(ii)堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
#include<stdio.h>
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("请输入面值数：");