北大屈婉玲算法分析与设计-习题解答5

Exercise2要求：对变量给出说明，动态算法要给出优化函数的递推方程、标记函数等，并给出时间复杂度分析。是否需要写伪码，看题目要求。对于给定实例，求出这个实例的解。1.有n个底面为长方形的货柜需要租用库房存放.如果每个货柜都必须放在地面上，且所有货柜的底面宽度都等于库房的宽度，那么第i个货柜占用库房面积大小只需要用它的底面长度li来表示，i=1,2,…,n.设库房总长度是L，且Llnii∑=1.设库房单位长度的租金是常数c，如果要求库房出租的收益达到最大，如何选择放入库房的货柜？设计一个算法求解这个问题，给出算法的伪码描述.2.设有n种不同面值的硬币，第i种硬币的币值是vk(其中v1=1)，重量是wi，i=1,2,…,n且现在购有某些总价值为y的商品，需要用这些硬币付款，如果每种钱币使用的个数不限，问如何选择付款的方法使得付出钱币的总重量最轻？设计一个求解该问题的算法.假设问题的输入实例是：v1=1,v2=4,v3=6,v4=8w1=1,w2=2,w3=4,w4=6y=12给出算法在该实例上计算的备忘录表和标记函数表，并说明付线的方法.3.有n项作业的集合J={1,2,…,n}，每项作业i有加工时间t(i)∈Z+，效益值v(i)，任务的结束时间D∈Z+，其中Z+表示正整数集合.一个可行调度是对J的子集A中任务的一个安排，对于i∈A，f(i)是开始时间，且满足下述条件：f(i)+t(i)≤f(j)或者f(j)+t(j)≤f(i),j≠ii,j∈ADktAk≤∑∈)(设机器从0时刻开动，只要有作业就不闲置，求具有最大总效益的调度.给出算法的伪码.4.把0-1背包问题加以推广.设有n种物品，第i种物品的价值是vi,重量是wi，体积是ci，且装入背包的重量限制是W，体积是V.问如何选择装入背包的物品使得其总重不超过W，总体积不超过V且价值达到最大？5.有n个分别排好序的整数数组A0，A1,…,An－1，其中Ai含有xi个整数，i=0,1,…,n－1.已知这些数组顺序存放在一个圆环上，现在要将这些数组合并成一个排好序的大数组，且每次只能把两个在圆环上处于相邻位置的数组合并.问如何选择这n－1次合并的次序以使得合并时总的比较次数达到最少？