文档介绍：实验3 动态规划
一、实验目的
1)熟练掌握动态规划思想及教材中相关经典算法。
2)掌握用动态规划解题的基本步骤,能够用动态规划解决一些问题。
二、实验内容
1)选定实验题目,仔细阅读实验要求,设计好输入输出,按照动态规划方法的思想构思算法,选取合适的存储结构实现应用的操作。
2)设计的结果在Visual C++ 实验环境下实现并进行调试。
3)实验要有详细的测试记录,包括各种可能的测试数据。
三、实验问题
(1)找零钱问题
«问题描述
设有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。
« 结果输出
程序运行结束时,。
输入文件示例
输出文件示例

3
12 5
9
3
复杂性:
需要另外的的空间存放暂时结果,空间复杂行为:
变量:
int n //零钱面值数目
int *price //存放零钱面值数组,下标表示第几种币值,数组内为币值价值
int *ret //存放存放临时结果数组,下标表示第几种币值,其值为对应个数
int sum //所需币值总数
函数:
int change(int total, int array[],int begin,int end)
//找零钱递归函数,包含要找的零钱总值,零钱面值数组,指向最大面值的指针,指向最小面值的指针,当找到所需最少硬币数返回1,找不到返回0
流程:
完整实验程序
#include <>
#include <>
#include<>
int *price;
int *ret;
int change(int total, int array[],int begin,int end)
{
if(total == array[begin])//最大的面值就是要找的零钱总值,所需零钱数+1
ret[begin]++;
else{
while(begin<end) //在币值范围内从大找到小
{ if(total>array[begin]){//要找的零钱总值比最大的面值大
ret[begin]++; //先设定可以有一张最大面值的零钱 if (change(total-array[begin],array,begin,end)) //剩余要找的零钱总值(减去最大面值),递归调用找出其所需零钱个数
return 1;
else //若递归找不到其剩余总值的所需最少零钱数,即不能凑齐,该面值不