习题3.1 证明②小问如下: 问题的解用解向量表示(见题目说明) 设按照该贪心策略选择的解为X={x,x2,…,xn},选中的文件集合即为Q,这些文 件按照长度从小到大存放到磁带上,记其排列为8=i1i2…is,k为Q选中的文件数 设该问题的一个最优解为Y={y1,y2,…,yn},选中的文件集合即为W。现证明Q的 文件个数不少于W(注意,对选中的文件个数进行证明是本题证明的关键,不是证选中了 具体哪个文件) 由于∑a≤L,所以Y集合里被选中的文件可以全部放进磁带,而且与其放的先后次 序无关(这也是问题的关键,只要顺序存放,长度总和都是一样的)。故将W中文件按照长 度从小到大排个序,得到一个按照文件长度从小到大的一个排列 r1r2…rn,m为W选 中的文件数,该排列可以放到磁带上。 1)如果8=8’,则X=Y,即X和Y选中同样的文件,Q是问题选中的最大子集。得 2)如果8≠δ’,则记j是i≠r的最小下标。根据i的选择方式(按文件长度从小 到大选择),a<=a-,否则在Q中一定是先选r;这个作业,而不是选i ●如果i∈W,则其长度a;=a-,此时,设ra=ij,则在δ中调换ra与r;,可以消去 位置的不同点 ●否则,i不在W中,由于其长度有a<=an,所以在δ中去掉r,而选择i,得到 个新文件集合W’,这个集合同样满足长度的限制,而且文件个数不会少于W。总之也可以 消去j位置的不同点。 经过以上调整,最终将W变得和Q一样,其文件个数不少于问题的最优解W,问题得 ,Q是问题选中的最大子集。 当今,“优化”无疑是一个热门词。做宏观经济规划要优化资源配置,搞企业经 营管理要优化生产计划,作新产品设计要优化性能成本比。就是在人们的日常生 活中,优化的要求也比比皆是,消费时,如何花尽可能少的钱办尽可能多的事, 出行时,如何走最短的路程到达目的地,等等。总而言之,在经济如此发展,竞 争如此剧烈,资源日渐紧张的今天,人们做任何事,无不望求事半功倍之术 求或提效、或增收、或节约等等之目标。所有类似的这种课题统称为最优化问题, 研究解决这些问题的科学一般就总称之为最优化理论和方法,另外也可用学术味 更浓的名称:“运筹学”。由于最优化问题背景十分广泛,涉及的知识不尽相同, 学科分枝很多,因此这个学科名下到底包含哪些分枝,其说法也不一致。比较公 认的是:“规划论”(包括线性和非线性规划、整数规划、动态规划、多目标规 划和随机规划等),“组合最优化”,“对策论”及“最优控制”等等。 从数学上比较一般的观点来看,所谓最优化问题可以概括为这样一种数学模 型:给定一个“函数”,F(X),以及“自变量”X应满足的一定条件,求X为怎习题 3.1 证明②小问如下： 问题的解用解向量表示（见题目说明） 设按照该贪心策略选择的解为 X＝{x1，x2，…，xn}，选中的文件集合即为 Q，这些文 件按照长度从小到大存放到磁带上，记其排列为 δ＝i1i2…ik，k 为 Q 选中的文件数 设该问题的一个最优解为 Y＝{y1，y2，…，yn}，选中的文件集合即为 W。现证明 Q 的 文件个数不少于 W（注意，对选中的文件个数进行证明是本题证明的关键，不是证选中了 具体哪个文件）。 由于    Pi W ai L ，所以 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 为怎