算法与设计六套试卷(9)

while (1) while x[k]

x[k]= (2) if place(k) then if k=n then flag=true；output x[1..n] else k= (3) (4) end if end if end while (5) end while if not flag then output “No solution” end NQUEENS 过程 place (k) //判断第k行皇后是否与前k-1行皇后冲突，是则返回false, 否 //则返回true。 …… end place 3. （14分）下面是解可复选的背包问题的动态规划算法。 问题描述：有一个容量为C的背包和n种物品，每种物品的个数都是无限的。设第i种物品的体积和价值分别为si和vi，C, si, vi都是正整数，i=1,2,…,。在这n种物品中选择物品装入背包，使得 41

装入背包的物品总价值最大。设每种物品都可选择任意个装入背包。 设f[i, j]表示背包容量为j，在第1~i种物品中进行选择的可复选背包问题的最优值，则 ??0 , i?0 f[i, j]??max{f[i?1, j-k*s]?k*v} , i?0 ii??0?k??j/si?算法 KNAPSACK 输入：物品种数n, n种物品的体积数组s[1..n]和价值数组v[1..n], 背包容量C。 输出：装入背包物品的最大总价值maxv，以及存储最优解信息的数组 H[0..n, 0..C]。 f[0..n, 0..C]=-1 maxv=knapsack(n, C) return maxv , H end KNAPSACK 过程 knapsack(i, j) //从第1~i种物品中选择物品装入容量为j的背包中，求背包中物品//所能达到的最大总价值并返回，同时将最优解的相应信息存入数//组H[0..n, 0..C]。 if f[i, j]= (1) then if i=0 then f[i,j]=0 else max=knapsack(i-1,j) k0=0; j1=j; v1=0 for k=1 to ?j/s[i]? j1=j1-s[i]; v1=v1+v[i]

42

a= (2) ＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ ＿ 信 ＿ ＿ ＿ 业 专订 ＿ 生 ＿ ＿ ＿ ＿ ＿ 系 考＿装＿＿＿＿＿院学＿＿＿＿＿＿

if a>max then max=a (3) end if end for f[i, j]= (4) (5) end if end if return f[i, j] end knapsack 算法 KNAPSACK_SOLUTION 输入：物品种数n , 背包容量C, n种物品的体积数组s[1..n], 相应的可复选的背包问题的最优解信息数组H[0..n, 0..C]。 输出：相应的可复选的背包问题的最优解x[1..n]。 y=C; x[n]=H[n, C] for i=n-1 to 1 y= (6) x[i]= (7) end for return x[1..n] end KNAPSACK_SOLUTION 43

四．算法设计题（15分） 1. 设有n种不同面值的硬币，面值分别为c1, c2, ? , cn，ci?1=sici，si为正整数，i=1, 2, …, n-1，每种硬币的个数不限，要求用最少个数的硬币，兑换价值为m的钱（m为非负整数），给出用贪心法求解该最优化问题的贪心选择策略，写出求最优值和最优解的贪心算法，并分析算法的时间复杂性。 福建师范大学数学与计算机科学学院

2006 — 2007学年第二学期考试 C 卷

44

＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 45