算法分析 - 综合性设计性实验 - 动态规划法 - 实验报告

精品文档 你我共享

综合性、设计性实验报告

姓名 周紧 学号200908001157

专业 计算机科学与技术 班级 09 级 01 班 实验课程名称 算法设计与分析 指导教师及职称 吕兰兰 讲师 开课学期 2011 至 2012 学年 上 学期 上课时间 2011年 12 月 7 日

湖南科技学院教务处编印

AAAAAA

精品文档 你我共享

实验名称： 用动态规划法来求解最少硬币问题。 实验时间： 2011-12-2 一、实验设计方案

AAAAAA

精品文档 你我共享

小组合作： 是○ 否● 小组成员： 1、实验目的： 1）理解回溯法的深度优先搜索策略 2）掌握用回溯法解题的算法框架 3）针对具体问题，能应用回溯法设计有效算法 4）用C++实现算法，并且分析算法的效率 2、实验设备及材料： 硬件设备：PC机 操作系统：win7 开发工具：vc++6.0 3、实验内容 最少硬币问题 问题描述 设有n种不同面值的硬币，各个硬币的面值存于数组T[1:n]中，现在要用这些面值的硬币来找钱，可以使用的各种面值的硬币个数存于数组Coin[1:n]中。 对于任意钱数0<=m<=20001，设计一个用最少硬币找钱m的方法。 算法设计：对于给定的1<=n<=10,硬币面值数组T和可以使用的各种面值的硬币个数数组 Coins,以及钱数m，0<=m<=20001，就算找钱m的最少硬币数. 数据输入：由文件input.txt提供输入数据，文件的第一行中只有一个整数给出n的值，第二行起每行2个数，分别是T[j]和Coin[j]，最后一行是要找的钱数m。 结果输出：将计算出的最少硬币数输出到文件output.txt，问题无解时输出-1。 输入文件示例 输出文件示例 input.txt output.txt 3 5 1 3 2 3 5 3 18 AAAAAA

精品文档 你我共享

程序代码： #include #include #include using namespace std ; struct Coin { int value ; int num ; }T[11] ; int comp(Coin a ,Coin b ) { return a.value <= b.value ; } int main() { int i ; int n ; int m ,sum ; ifstream fin; fin.open(\ fini>>n; while(n != EOF) { for( i = 0 ; i < n ; i ++ ) fin>>T[i].value>> T[i].num; fin>>m; sort(T,T+n ,comp ); sum = 0 ; int k = -1 ; for( i = n-1 ; i >=0 ; i-- ) { if( T[i].value <= m ) { k = i ; break; } } for( i = k ; i >= 0 ; i -- ) { while( T[i].num > 0 && m >= T[i].value ) { AAAAAA