算法设计及分析P3-.pdf

《算法设计及分析P3-.pdf》由会员分享，可在线阅读，更多相关《算法设计及分析P3-.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.-问题描述问题描述设有 n 种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。1当只用硬币面值 T1,T2,Ti时，可找出钱数 j 的最少硬币个数记为 C(i,j)。假设只用这些硬币面值，找不出钱数j 时，记 C(i,j)=。给出 C(i,j)的递归表达式及其初始条件。其中，1in,1jL.(2)设计一个动态规划算法， 对于 1jL， 计算出所有的 C(n,j).算法只允许使用一个长度为L的数组。 用L和n作为变量表示算法的时间复杂性。3在 C(n,j),1=j=L，已计算出的情况下，设计一个贪心算法，对任意钱数m=L，给出用最少

2、硬币找钱 m 的方法。当 Cn,m时，算法的计算时间为 O(n+C(n,m)。分析分析这个问题用动态规划来解，归结到动态规划上面就变成了无限背包问题。区别在于，现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是一样的，即每次选择都可以选择任何一种硬币。首先，找零钱问题具有最优子构造性质：兑换零钱问题的最优子构造表述： 对于任意需要找的钱数 j， 一个利用 Tn中的 n 个不同面值钱币进展兑换零钱的最正确方案为P(T(1),j)，P(T(2),j),.,P(T(n),j)，即此时的最少钱币个数 C(n,j)P(T(2),j),.,P(T(n),j)一定是利用 Tn中 n 个不同的面值

3、钱币对钱数j=j-P(T(1),j)* T(1)进展兑换零钱的最正确方案。其次，找零钱问题具有重叠于问题性质：那么. word.zl-.-a)当 n=1 时，即只能用一种钱币兑换零钱，钱币的面值为T0，有2 根据分析建立正确的递归关系递归关系：复杂度：复杂度：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为：O(n2)；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：O(n2)算法：算法：#include. word.zl-.-#includeusing namespace std;#define MAX 20002#define INF 99999

4、99#define min(a,b) (a)(b)?(b):(a)int T11,Coins11,n;/硬币面值数组 T,可以使用的各种面值的硬币个数数组Coins,n 种不同面值的硬币int cMAX;/数组 c存放要找的最少硬币个数int m; /要找的钱数 mvoid init()int i;coutn;coutn 输入硬币面值及其此面值硬币的个数：endl;for(i=0;iTiCoinsi;coutm;. word.zl-.-int main(int argc, char *argv)init();for(int i=0;i=m;+i)ci=INF;c0=0;for(int i=0;

5、in;+i)for(int j=1;j=Ti;-k)ck=min(ck,ck-Ti+1);if(cm!=INF)coutn 最少硬币个数为：cmendl;elsecout-1endl;return 0;. word.zl-.-运行结果：运行结果：时间复杂度：从上面算法可知，最优值 cj的计算过程中，最外层为循环for(j=1;j1&flag=0)循环，而while(k1&flag=0)循环中又嵌套着三个并列的 for 循环。因此本算法最坏情况下的复杂度是 O(L*2n)； 最好的情况当然是里面 for 循环的条件不满足而不执行，此时的复杂度为O(L*n)。其中：L 表示需要兑换的零钱数， 对于

6、 L 来说， 该值一般不是很大， 对于钱币来说， L 会小于 100元，即 10 000 分；n 表示钱币的种类，n 值一般不会很大如钱币总的有 13 种(从 1 分，2 分，100 元)。经过以上分析，如是最坏情况时的复杂度应为O(L*2n),那么该值对于存和运行速度较小的自动售货机等的应用前景那么不会很好。但本算法中的递归构造在LTn时，有. word.zl-.-可见对于钱币 j=L 时，求 c(n,j)时，并不要求对从 1ij，的所有情况都要求 c(n,i)+1，而是只求。其中：1kn。钱币一般只有13 种左右，因此其效率大为上升。最坏的情况下需要执行而 M 小于 100 元即 1000

7、0 分， 远大于 n。本算法的动态规划算法的时间复杂性比该问题的一般动态规划算法的效率要好得多。该算法的时间复杂性是 103数量级的对于应用于自动售货机等运行速度较慢的机器来说是不成问题的。贪心算法贪心算法由贪心算法可知尽量用大面值的硬币组合来找钱， 可以使使用的硬币最少。 而贪心算法对最少硬币问题的解决总是可以得到最优解很好的近似解。例如：9 分面值的硬币 5 枚，8 分面值的硬币 5 枚， 2 分面值的硬币 8 枚，要找 25 分钱。设要找的钱为 m，硬币种类为n，ti(0i=n)为硬币的面值，ci为可以使用的各种面值的硬币个数, ki为第 i 种面值的硬币可以使用的最多个数ki=minm

8、/ti,ci(1)将硬币依面值大小排序9 8 2(2)按面值种类划分不同情况. word.zl-.-有多少种面值就划分多少种情况. 每种情况的第一枚硬币面值各不一样,其后对剩余的硬币按面值从大到小排列.划分为三个情况：982，892，298。对应 ki为：k0=3, k1=3 ,k2=8得到近似最优解群为 9 分 1 枚,8 分 2 枚;9 分 1 枚,8 分 1 枚,2 分 4 枚;9 分1 枚,2 分 8 枚.算法优化1,在寻找最优组合过程中，有些情况可以不予考虑。比方上例中2 9 82,在以小面值的硬币为第一个的情况中，在寻找最优组合时，会遇到两种情况： a、使用硬币个数要比以大面值的硬

9、币(如 9 和 8)为第一个的情况大得多。 b、寻找到的组合与前面的情况有重复。完整程序代码如下：#include #include #includeint n,money;. word.zl-.-struct ctype int value; int coin;templatevoid make2Darray(type * * &x,int rows,int cols) x=new type *rows; for(int i=0;irows;i+) xi=new typecols;void swap(ctype &a,ctype &b)ctype temp;temp=a;a=b;b=temp

10、;int partition(ctype array,int p,int r)int i,j;. word.zl-.-ctype key;i=p;j=r+1;key=arrayp;while(true)while(array+i.valuekey.value);if(i=j) break;swap(arrayi,arrayj);arrayp=arrayj;arrayj=key;return j;void quicksort(ctype array,int p,int r)int q;if(pn; int * coins=new intn+1; ctype * T=new ctypen+1; f

11、or(int i=1;iTi.value; inputTi.coin; inputmoney;quicksort(T,1,n);/*for(i=1;i=n;i+)coinsi=Ti.coin;*/ int max=0;. word.zl-.- for(i=1;i=n;i+) max+=Ti.coin; max+=10; int * min=new intmoney+1; min0=0;int * *um; make2Darray(um,money+1,n+1); for(i=0;i=money;i+) for(int j=1;j=n;j+)umij=0;if(T1.value=1) min1=

12、1;um11=1;else min1=max; int j=2; while(j=money) minj=max; i=1; while(i=Ti.value) int coinumber=umj-Ti.valuei; coinumber+; if(minj1+minj-Ti.value)&(coinumber=Ti.coin) . word.zl-.-for(int k=1;k=n;k+)umjk=umj-Ti.valuek; umji+;minj=1+minj-Ti.value; i+; j+; if(minmoney!=max) outputminmoney; else output-1;. word.zl-