云南开放大学算法设计与分析第八章 动态规划

习题

1. 某企业新进三套生产设备，将下发到三个生产车间A、B、C，在未获得生产设备前及获得1、2、3套设备后，各自的生产利润如下表所示，x表示下发生产设备的数量，求使得三个生产车间利润总和最大的分配方案。

x	A	B	C			x	A	B	C
0	2	5	8			2	7	16	17
1	4	10	12			3	11	20	22

 

2. 找出由n个数组成的序列的最长单调递增子序列。

 

3. 设有n项任务，加工时间分别表示为正整数t₁, t₂, …, t_n。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就不得闲置。如果直到时刻T所有任务都完成了，总的加工时间就等于T。设计一个算法找到使得总加工时间T达到最小的调度方案。设给定实例如下：

t₁=1, t₂=5, t₃=2, t₄=10, t₅=3

试给出一个加工时间最少的调度方案，给出计算过程和问题的解。

 

4. 设有n种不同面值的硬币，第i种硬币的币值是v_k（其中v₁=1），重量是w_i，i=1,2,…,n。现在购买总价值为y的某些商品，需要用这些硬币付款，如果每种钱币使用的个数不限，问如何选择付款的方法使得付出钱币的总重量最轻？设计一个求解该问题的算法，并分析算法的时间复杂度，假设问题的输入实例是：

v₁ =1， v₂=4， v₃=6， v₄=8

w₁ =1， w₂ =2， w₃=4， w₄=6

y=12

在问题分析阶段，请给出算法在该实例上每一阶段计算结果，形成一张备忘录表格。

 

5. 把0-1背包问题加以推广。设有n个物品，第i物品的价值是v_i，重量是w_i，体积是c_i，且装入背包的重量限制是W，体积是V。问如何选择装入背包的物品使得其总重不超过W，总体积不超过V且价值达到最大？设计一个动态规划算法求解这个问题，说明算法时间复杂度。