algorithm-homework..doc

Design and Analysis of Algorithms (12 Spring) Due: Apr. 24, 2012 Arrange the following functions in ascending asymptotic order of growth rate: ，，，，. Given currency denominations: 1,5,10,25,100, devise a method to pay amount x to customer using fewest number of coins. 解：方法1（使用贪心算法）：表达式：mincoin(p,x,c)=mincoin(p,x-max,c)+1; max为p中小于x的最大值，如果p中的最小值都大于x，返回p[0]. n?硬币种类数， p ?{1,5,10,25,100}; //初始化（p中数值从小到大排序） C?空，k?0; //C用于保存需要的硬币，k需要的硬币数 while（x0）{ max?find(p,x); //find(p,x)从p中找出小于x的最大面值,找不到返回p[0] x?x-max，k?k+1，C?max；} if(x==0) 输出C，k，否则输出impossible。 分析：贪心算法并不一定总能找到最优的解，在某些情况下甚至不能找到一个解（例如：由面值3，5，9面值的币组成10），当然在本例下总能找到解，但并不保证是最优的。 方法2（使用动态规划）：表达式：mincoin(p[i],x,result,record)= min{mincoin(p[i-1],x-t*p[i], result,record)+t, mincoin(p[i-1],x, result,record)} //result[i][j]用于保存从面值为p[0]--p[i]的硬币中选取凑成钱数j+1的最少硬币 //数，record[i][j]保存需要面值为p[i]的硬币的数量。 n?硬币种类数， p ?{1,5,10,25,100}; //初始化（p中数值从小到大排序） result[n][x]?x+1，record[n][x]?0; //对数组中的每个元素初始化 for（i=0 to n） for（j=0 to x） //均左闭右开 if(存在从面值为p[0]--p[i]的硬币中选取凑成钱数j+1的最少硬币数m) result[i][j]?m, record[i][j]?temp; //temp为需要p[i]的数量 if(result[n-1][x-1]x) 则表示不能凑成x，退出，否则接着执行 输出result[n-1][x-1]；// 输出最少钱币数 while(x0){ //输出面值 如果record[n-1][x-1]大于0，输出record[n-1][x-1]个p[n-1],否则转9； x=x- record[n-1][x-1]*p[n-1], n=n-1; n=n-1;} 分析：该方法可以找到最优解，但是时间复杂度和空间复杂度都要比方法一大。 An algorithm solves problems of size n by dividing it into three subproblems of size n/2, recursively solving each subproblems, and then combine the solutions in time. Can you analyze the running time of this algorithm? 解：假设用T(n)表示解决size为n的问题所用的时间，那么解决三个size为n/2的子问题所用的时间为3*T(n/2)，由于分治之后组合结果所用的时间为n2，所有分治后所用的时间(假设为F(n)) F(n)= 3*T(n/2)+ n2=MAX{O(T(n/2)), O(n2)} Please using dynamic programming to solve the following knapsack problem. We are given 7 items and a knapsack. Each item i has weight of wi 0 kilograms and value of vi 0 dollars (given in table 1). The capacity of the knapsack is 14 kilograms. Then how to fill the knapsack to maximize the total value? Items Weight Value 1 3 2