习题3.1
证明②小问如下：
问题的解用解向量表示（见题目说明）
设按照该贪心策略选择的解为X＝{x1，x2，…，xn}，选中的文件集合即为Q，这些文件按照长度从小到大存放到磁带上，记其排列为δ＝i1i2…ik，k为Q选中的文件数设该问题的一个最优解为Y＝{y1，y2，…，yn}，选中的文件集合即为W。现证明Q的文件个数不少于W（注意，对选中的文件个数进行证明是本题证明的关键，不是证选中了具体哪个文件）。
由于，所以Y集合里被选中的文件可以全部放进磁带，而且与其放的先后次序无关（这也是问题的关键，只要顺序存放，长度总和都是一样的）。故将W中文件按照长度从小到大排个序，得到一个按照文件长度从小到大的一个排列δ’ ＝r1r2…rm，m为W选中的文件数，该排列可以放到磁带上。
1）如果δ＝δ’，则X＝Y，即X和Y选中同样的文件，Q是问题选中的最大子集。得证。
2）如果δ≠δ’，则记j是ij≠rj的最小下标。根据ij的选择方式（按文件长度从小到大选择），aij<=arj，否则在Q中一定是先选rj这个作业，而不是选ij。
● 如果ij∈W，则其长度aij=arj，此时，设rd=ij，则在δ’中调换rd与rj，可以消去j位置的不同点
● 否则，ij不在W中，由于其长度有aij<=arj，所以在δ’中去掉rj，而选择ij，得到一个新文件集合W’，这个集合同样满足长度的限制，而且文件个数不会少于W。总之也可以消去j位置的不同点。
经过以上调整，最终将W变得和Q一样，其文件个数不少于问题的最优解W，问题得证。
，Q是问题选中的最大子集。
当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法，另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。
从数学上比较一般的观点来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。这里在函数和自变量两个词上之所以打上引号，是想强调它们的含意比中学数学和大学微积分中函数的定义要广泛得多。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型，它还可以利用数学符号更简洁地表示成：Min F(X)或Max F(X)。
解决最优化问题的关键步骤是，如何把实际问题抽象成上述数学模型，也就是构造出目标函数与约束条件。一但这一步完成，对于简单问题，可借图形或微积分来求解。遇到比较复杂的课题，可先搞清它属于运筹学哪一分枝，并在此基础上尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica,Lindo,Lingo等，来计算。下面举一个简单例子来具体说明这个关键步骤。
证明②小问如下：
问题的解用解向量表示（见题目说明）
设按照该贪心策略选择的解为X＝{x1，x2，…，xn}，选中的文件集合即为Q，这些文件按照长度从小到大存放到磁带上，记其排列为δ＝i1i2…ik，k为Q选中的文件数设该问题的一个最优解为Y＝{y1，y2，…，yn}，选中的文件集合即为W。现证明Q的文件个数不少于W（注意，对选中的文件个数进行证明是本题证明的关键，不是证选中了具体哪个文件）。
由于，所以Y集合里被选中的文件可以全部放进磁带，而且与其放的先后次序无关（这也是问题的关键，只要顺序存放，长度总和都是一样的）。故将W中文件按照长度从小到大排个序，得到一个按照文件长度从小到大的一个排列δ’ ＝r1r2…rm，m为W选中的文件数，该排列可以放到磁带上。
1）如果δ＝δ’，则X＝Y，即X和Y选中同样的文件，Q是问题选中的最大子集。得证。
2）如果δ≠δ’，则记j是ij≠rj的最小下标。根据ij的选择方式（按文件长度从小到大选择），aij<=arj，否则在Q中一定是先选rj这个作业，而不是选ij。
● 如果ij∈W，则其长度aij=arj，此时，设rd=ij，则在δ’中调换rd与rj，可以消去j位置的不同点
● 否则，ij不在W中，由于其长度有aij<=arj，所以在δ’中去掉rj，而选择ij，得到一个新文件集合W’，这个集合同样满足长度的限制，而且文件个数不会少于W。总之也可以消去j位置的不同点。
经过以上调整，最终将W变得和Q一样，其文件个数不少于问题的最优解W，问题得证。
，Q是问题选中的最大子集。
当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法，另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。
从数学上比较一般的观点来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。这里在函数和自变量两个词上之所以打上引号，是想强调它们的含意比中学数学和大学微积分中函数的定义要广泛得多。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型，它还可以利用数学符号更简洁地表示成：Min F(X)或Max F(X)。
解决最优化问题的关键步骤是，如何把实际问题抽象成上述数学模型，也就是构造出目标函数与约束条件。一但这一步完成，对于简单问题，可借图形或微积分来求解。遇到比较复杂的课题，可先搞清它属于运筹学哪一分枝，并在此基础上尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica,Lindo,Lingo等，来计算。下面举一个简单例子来具体说明这个关键步骤。
