Algorithm（15）
问题分析：
该问题等价于最优化问题，即现在有N个任务，每个任务需要一个时间区间ti来处理。每个任务i可以灵活处理，只要在规定的截止时间di之间完成处理就行，即任务i在时间段～di
-ti的任意一个时刻，并且要求一个长度为ti连续的时间区间。虽然如此，但是因为只有一个资源来完成任务，所以不同的任务要求被分在完全不重叠的区间。 & &在这种情况下，根据想要优化的目标，应该存在许多的优化方法。简单而有效优化方法，考虑一个非常自然的通过贪心算法可以被优化的目标。有几种自然的贪心方法，在这些方法中我考虑任务的数据有，并且按照某种简单的规则对他们排序。
一种方法是把任务按长度ti增长的次序安排，使得较短的任务尽快结束。但是它完全忽略了任务的截止时间。例如，题目中提供的作业D，完成它所需的时间为1，最短，但是它的截止时间为7，而其他的作业虽然完成他们所需的时间较长，但是截止时间较短。如果要想尽可能多得完成任务，显然安排先完成作业D不巧当，而安排先完成其他的作业比较合适。因此该规则的最优化规则失效。
根据1的分析我们应该可以考虑先完成(diti)非常小的任务，这种任务是那种需要用最小松弛时间开始的任务，即先安排完成可调整时间最短的作业。因此将按照diti增长的次序对任务排序。但是，这种贪心规则也不是最优的。考虑两个任务的实例，假设有3个任务，他们的截止时间和完成任务所需的时间分别为（1）8和7，（2）4和2，（3）5和3，那么按照2的规则，先选择任务（1），那么最终完成的任务只有任务（1），完成的任务数量也只有1；而选择任务（2）或者（3），那么可以在规定的时间内可以完成任务（2）和（3），完成的任务数量为2.因此该规则也失效。
综合考虑di和ti。因为每个任务只要在它的截止时间之前完成即可，而不需要该什么时候开始，那么要想完成更多的任务，先完成截止时间较短的任务，并放弃已超过截止时间的任务。一般来说，截止时间小的作业暗示着完成该作业所需的时间也少，反之不一定成立。因此要想完成更多的作业，那么需要在作业的截止时间之前一个一个的完成它。总之，优化的思路为：a.在未完成的任务中，选择截止时间较早的任务，记为
i，若完成其所需的时间ti小于它的截止时间di，那么放弃完成该任务，继续a步骤，否则，就选择完成该任务，并且更新剩下未完成任务的截止时间，即将它们的截止时间减去完成前一个任务所需的时间，继续a步骤。根据该规则写出该算法：
i.初始化定义&&
定义一个2维数组 Task[3][NUMOFTASK]。其中第一行的元素表示任务i的截止时间，第二行的元素表示完成任务i所需时间，第三行表示任务i的代号（因为排序，所以需要记住其任务代号1..
NUMOFTASK）。这里NUMOFTASK表示任务数量。为了简单表示符号，用三个一维数组Task0 [NUMOFTASK]
， Task1 [NUMOFTASK]， Task2[NUMOFTASK]表示 Task[3][NUMOFTASK]
对应的第、1、2行；& &
完成任务代号数组FinishedTask[NUMOFTASK],初始化全为（如果FinishedTask[]数组元素值为任务代号i，表示完成了任务i）。&
已完成任务数量SumOfFinishedTask=0.
& & & &a.将所有的任务按照截止时间从小到大排序。若存在截止时间相同的情况，那么进一步按照其对应的完成所需时间从小到大排序。根据第一行排好序为： Task1[0]&= Task1[1]...&=
Task1[NUMOFTASK-1](对应的Task1[]、Task2[]对应的元素位置也更改好)。
& & & & & & & &b.
按照Task0[]的次序考虑任务i，i从1到NUMOFTASK(或者是～NUMOFTASK-1)&
&将Task0[i]与Task1[i]进行比较，& &&
& & & & & & & & & & b1.若小于，那么跳过，重复b；& &&
& & & & & & & & & & b2.若大于等于，那么执行该任务，并且 & & & &&
& & & & & & & & & & & & & b21将Task2[i]录入以完成任务的数组，同时SumOfFinishedTask加1.
& & & & & & & & & & & & & b22.j从i+1到NUMOFTASK（这里表示未完成的任务），& & & & & & &&
& & & & & & & & & & & & & & & & &b221更新截止时间，即用当前的截止时间减去完成任务i所需要的时间，Task1[j]=Task1[j]-Task2[i]
& & & & & & & c.打印完成任务总数SumOfFinishedTask，并根据它打印出完成的任务的顺序即其代号结束。
代码实现：
#include &stdio.h&
#define NUMOFTASK 5
void swap(int *a,int *b)
int temp=*a;
int partition(int *r, int first, int end)
while (i&j)
while (i&j&&*(r+i)&=*(r+j))
if(*(r+i)==*(r+j))//如果两者的截止时间相等，那么需要接着比较完成他们所需要的时间
if(*(r+i+2*NUMOFTASK)&*(r+j+2*NUMOFTASK))
swap((r+i),(r+j));
swap((r+i)+NUMOFTASK,(r+j)+NUMOFTASK);
swap((r+i)+2*NUMOFTASK,(r+j)+2*NUMOFTASK);
while (i&j&&*(r+i)&=*(r+j))
if(*(r+i)==*(r+j))//如果两者的截止时间相等，那么需要接着比较完成他们所需要的时间
if(*(r+i+2*NUMOFTASK)&*(r+j+2*NUMOFTASK))
swap((r+i),(r+j));
swap((r+i)+NUMOFTASK,(r+j)+NUMOFTASK);
swap((r+i)+2*NUMOFTASK,(r+j)+2*NUMOFTASK);
void QuickSort(int *r,int first,int end)
if(first&end)
int pivot=partition(r, first, end);
QuickSort(r, first, pivot-1);
QuickSort(r, pivot+1, end);
int main (int argc, const char * argv[])
int DueTime[][NUMOFTASK]={{8,3,3,7,4},{1,2,3,4,5},{5,2,2,1,2}};//DueTime数组元素第一行代表一个任务的截止时间，第二行代表任务的代号,第三行代表完成任务所需的时间，仅供排序用
int TimeToFinish[NUMOFTASK]={5,2,2,1,2};//TimeToFinish数组元素代表任务所需的时间
int FinishedTask[NUMOFTASK]={0};//FinishedTask用来表示完成的任务代号，元素值为0表示没没完成任务
int SumOfFinishedTask=0;//记录完成任务的数量
//对DueTime数组元素的第一行元素进行快速排序，当DueTime中的截止时间有相同的情况时，按照对应的TimeToFinish元素从小到大排序，
//如果一个任务的截止时间与完成任务所需的时间一样，那么随机排序
QuickSort(*DueTime, 0, NUMOFTASK-1);
int i=0;//老的编译器不支持在for语句中定义变量
for(i=0;i&NUMOFTASK;i++)
if(DueTime[0][i]&=TimeToFinish[DueTime[1][i]-1])//截止时间大于等于任务所需时间，那么就可以顺利执行完该任务
FinishedTask[SumOfFinishedTask++]=DueTime[1][i];
int j=i+1;
for(;j&NUMOFTASK;j++)
DueTime[0][j]=DueTime[0][j]-TimeToFinish[DueTime[1][i]-1];//将剩下的任务的截止时间减下完成前一个任务所花的时间
//打印出完成的任务数量
printf(&completed:%d tasks!\n&,SumOfFinishedTask);
//打印出完成的任务的顺序即其代号
for (i=0; i&SumOfFinishedT i++) {
//if(FinishedTask[i]!=0)
printf(&step %d:\tFinished No.%d Task。\n&,i+1,FinishedTask[i]);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：723292次
积分：7343
积分：7343
排名：第1884名
原创：123篇
转载：35篇
评论：63条
(2)(2)(5)(8)(1)(1)(1)(1)(1)(1)(1)(4)(2)(5)(3)(12)(6)(8)(24)(26)(17)(33)catia设计宇通客车底盘座_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
catia设计宇通客车底盘座
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩3页未读，继续阅读
你可能喜欢课堂任Ġ设计一列式布局
课堂任Ġ设计一列式布局知识预读什么是DIVDIV是一个XHTML支持的标签，如当用户运用表格布局时，代码中会出现＜table&＜/table&这样的结构，当用户运用DIV时也会出现＜div&＜/div&这样的结构。DIV是XHTML中指定的，专门用于布局设计的容器对象。当用户运用DIV时，只需将内容（如文本、图像或其他标签）放到＜div&＜/div&中，如＜div&欢迎进入DIV+CSS的地盘＜/div&，但＜div&只是一个标签，只负责将内容标识为一个区域，不负责其他任何事情，如内容的修饰美化、位置摆放一般由CSS来控制。什么是DIV+CSS布局DIV+CSS布局可以用一句话来概括，运用DIV在网页上划出一块属于自己的地盘，运用CSS对这块地盘进行相应的排版、修饰和美化。DIV+CSS布局与传统表格（table）布局的区别在于：表格布局的定位都是采用表格，通过表格的间距或者用无色透明的GIF图片来控制布局版块的间距；而DIV+CSS布局采用层（div）来定位，通过层的margin，padding，border等属性来控制版块的间距，而这些属性一般由CSS来控制。如所示。2–1 表格布局与DIV+CSS布局的区别ID与CLASS的区别当用户在使用CSS的时候，通常会看到，不同的CSS定义却具有相同的效果，如所示。2–2 ID和CLASS定义和调用的区别那ID与CLASS的定义和使用有什么区别呢？区别在于同一个名称的ID值在当前XHTML页面中，只允许使用一次；而不管是应用DIV还是其他对象，CLASS都可以重复使用。什么是块级元素与内联元素块级元素一般是其他元素的容器元素，它可以容纳内联元素和其他块元素。内联元素一般都是基于语义级（semantic）的基本元素。内联元素只能容纳文本或者其他内联元素。如所示，表单是块级元素，而表单元素是内联元素。2–3 块级元素（表单）和内联元素（表单元素）的区别一般的块级元素诸如段落＜p&、标题＜h1&＜h2&、列表＜ul&＜ol&＜li& 、表格＜table&、表单＜form&、＜div&和＜body&等元素，内联元素则如表单元素＜input&、超级链接＜a&和图像＜img&等元素。块级元素的显著特点是：每个块级元素都是从一个新行开始显示，而且其后的元素也需另起一行进行显示。＜span&在CSS定义中属于一个行内元素，而＜div&是块级元素。如块级元素＜div&你好啊＜/div&，可以运用CSS来定义“你好啊”，但假如要定义其中的“好”字，那就可以用内联元素＜div&你＜span&好＜/span&啊＜/div&来单独定义。如所示。2–4 DIV与SPAN的区别之单独定义打个比方：行内元素＜span&相当一个小容器，而＜div&相当于一个大容器，如果想在大容器中装一些清水。但也想在里面装一些墨水，怎么办？很简单，把小容器拿出来装上墨水然后放入大容器里的清水中就可以了。什么是FLOAT在上面学习了什么是块级元素与内联元素，同样也知道＜div&是一个块级元素，当运用DIV+CSS布局的时候，多个＜div&将会竖向排列在一起，如所示。当需要其横向排列的时候，将会用到FLOAT这个属性，FLOAT属性作用就是改变块级元素对象的默认显示方式。BLOCK对象设置了FLOAT属性之后，它将不再独自占据一行。可以浮动到左侧或右侧。如所示。2–5 未添加FLOAT属性的DIV2–6 添加了FLOAT属性的DIV提示固定宽度布局和自适应布局的区别？固定宽度布局是指设计的网页布局不会随着浏览器的放大缩小而改变，自适应布局是指设计的网页布局将随着浏览器的放大缩小而改变。任务目标◆ 学会运用DIV+CSS设计一列式布局，效果如所示；2–7 一列式布局示意图◆ 学会如何设置布局的自适应效果和固定宽度效果。实施步骤步骤1　建立站点，准备素材用Dreamweaver 8软件创建一个Web站点，在站点内建立文件夹images和首页index.html，将素材放到文件夹images中。步骤2　设计整体页面属性在对整个页面布局之前，首先来设置整体网页的页面属性，打开index.html，单击菜单栏中的“窗口”|“CSS样式”命令，调出CSS样式面板，单击“新建CSS规则”按钮，弹出“新建CSS规则”对话框，进行如所示选择。2–8 “新建CSS规则”对话框单击“确定”按钮，弹出“保存样式表文件为”对话框，输入文件名“layout”，如所示。2–9 “保存样式表文件为”对话框单击“保存”按钮，弹出“body的CSS规则定义”对话框，选择“分类”|“方框”，在填充和边界选项中输入，如所示。2–10 “body的CSS规则定义”对话框选择“分类”|“类型”，大小选择ʯ素”，行高选择为ĝ”，修饰选择为“无”。单击“应用”、“确定”按钮；返回“插入DIV标签”，单击“取消”按钮。提示“应用”和“确定”的区别：“应用”表示可以选择某种效果后，在单击后直接看到效果，而如果不满意的话，可以直接更改，而“确定”表示直接使用该效果，如果不满意的话，需要再次打开对话框进行设计。步骤3　创建网页头部部分header在设置好页面整体属性之后，接下来要创建网页的整体布局框架，首先设计网页的header框架，header一般包括logo（网站标志），nav（网站导航）两个部分，创建时先建立一个header的DIV，然后在里面分别创建一个logo的DIV和一个nav的DIV。① 设置header在index.html中，选择工具栏中的“布局”，单击插入DIV标签按钮，弹出“插入DIV标签”对话框，在对话框中单击“新建CSS样式”按钮，弹出“新建CSS规则”对话框，进行如所示选择和输入。2–11 “新建CSS规则”对话框ġ单击“确定”按钮，弹出“＃header的CSS规则定义”对话框，在CSS定义页面中，选择“分类”|“方框”，输入宽为ʯ素”，高为ʯ素”，选择“分类”|“背景”，单击“浏览”按钮，选择文件夹images里header.gif文件，如所示。2–12 背景图像选择单击“确定”按钮，返回“插入DIV标签”对话框，单击“确定”按钮。然后删除页面中自动生成的“此处显示 id ＂header＂ 的内容”文字内容。② 设置logo选择工具栏中的“布局”，单击插入DIV标签，弹出“插入DIV标签”对话框，进行如所示设置。2–13 插入DIV标签位置选择ġ在对话框中单击“新建CSS样式”按钮，弹出“新建CSS规则”对话框，在选择器中输入“＃logo”，单击“确定”按钮。弹出“＃logo的CSS规则定义”对话框，选择“分类”|“方框”，输入宽为ʯ素”，高为ʯ素”；选择“分类”|“背景”，单击“浏览”按钮，选择文件夹images里logo.gif文件，单击“确定”按钮，返回“插入DIV标签”按钮，单击“确定”按钮。然后删除页面中自动生成的“此处显示id＂logo＂的内容”文字内容。③ 设置nav选择工具栏中的“布局”，单击插入DIV标签按钮，弹出“插入DIV标签”对话框，进行，如所示设置。2–14 插入DIV标签位置选择ġ在对话框中单击“新建CSS样式”按钮，弹出“新建CSS规则”对话框，在选择器中输入“＃nav”，单击“确定”按钮。弹出“＃nav的CSS规则定义”对话框，选择“分类”|“方框”，输入宽为ʯ素”，高为ʯ素”；选择“分类”|“背景”，单击“浏览”按钮，选择文件夹images里nav.gif文件，单击“确定”按钮，返回“插入DIV标签”对话框，单击“确定”按钮。然后删除页面中自动生成的“此处显示id＂nav＂的内容”文字内容。到此为止，已经设置好页面中header的框架。④ 输入导航栏中的栏目将光标置于ID为nav的DIV中，选择工具栏中的“文本”，单击项目列表，输入“个人爱好”，按回车键，“每日心情”，按回车键，“心灵驿站”。按回车键，可输入的内容都是竖排的，将它设置为横排。单击“窗口”|“CSS样式”命令，在“CSS样式”的工具栏中单击新建CSS规则按钮，弹出“新建CSS规则”对话框，如所示。2–15 “新建CSS规则“对话框ġ单击“确定”按钮。弹出“#header #nav li的CSS规则定义”对话框，选择“分类”|“方框”，进行如所示设置。2–16 “#header #nav li的CSS规则定义”对话框单击“确定”按钮。߼览，效果如所示。2–17 网页头部效果图步骤4　创建网页内容部分content在完成网页的头部之后，接下来创建网页内容部分content的框架。ġ网页内容部分content框架的创建选择工具栏中的“布局”，单击插入DIV标签，弹出“插入DIV标签”对话框，进行如所示设置。2–18 插入DIV标签位置选择ġ单击新建CSS规则按钮，弹出“新建CSS规则”对话框，在选择器中输入“#content”，单击“确定”按钮，弹出“#content的CSS规则定义”对话框，选择“分类”|“方框”，输入宽ʯ素”，高ʯ素”，选择“分类”|“背景”，进行如所示设置。2–19 “#content的CSS规则定义”对话框单击“确定”按钮，返回到“插入DIV标签”对话框，单击“确定”按钮。删除页面中自动生成的“此处显示id＂content＂的内容”文字内容。ġ网页内容部分content框架内容的填充① 填充内容页面中最上面的一张图像，建立一个DIV，并将该图片设置为背景。操作步骤如下：选择工具栏中的“布局”，单击插入DIV标签按钮，弹出“插入DIV标签”对话框，进行如所示设置；2–30 插入DIV标签位置选择ġ单击新建CSS规则按钮，弹出“新建CSS规则”对话框，在选择器中输入“#content1”，单击“确定”按钮，弹出“#content1的CSS规则定义”对话框，选择“分类”|“方框”，输入宽ʯ素”，高ʯ素”，选择“分类”|“背景”，进行如所示设置；2–31 “#content1的CSS规则定义”对话框单击“确定”按钮，返回到“插入DIV标签”对话框，单击“确定”按钮。删除页面中自动生成的“此处显示id＂content1＂的内容”文字内容。② 对正文内容进行图文混排，左上角为一张图像，其余地方均为文字，所以采用FLOAT方式来对图像进行设置以达到这种效果。操作步骤如下：选择工具栏中的“布局”，单击插入DIV标签按钮，弹出“插入DIV标签”对话框，进行如所示设置；2–32 插入DIV标签位置选择ġ单击新建CSS规则按钮，弹出“新建CSS规则”对话框，在选择器中输入“#content2”，单击“确定”按钮，弹出“#content2的CSS规则定义”对话框，选择“分类”|“方框”，输入宽ʯ素”，高ʯ素”，在边界选项中进行设置，设置上、右、下、左边界分别为ʯ素”、ʯ素”、ʯ素”、ʯ素”，单击“确定”按钮，返回到“插入DIV标签”对话框，单击“确定”按钮。删除页面中自动生成的“此处显示id＂content2＂的内容”文字内容；接下来为图像建立一个单独的DIV，选择工具栏中的“布局”，单击插入DIV标签按钮，弹出“插入DIV标签”对话框，进行如所示设置；2–33 插入DIV标签位置选择ġ单击新建CSS规则按钮，弹出“新建CSS规则”对话框，在选择器中输入“#img”，单击“确定”按钮，弹出“#img的CSS规则定义”对话框，选择“分类”|“方框”，输入宽ʯ素”，高ʯ素”，浮动设置为“左对齐”，勾选填充和边界的全部相同复选框，并设置填充为ʯ素”，边界为ʯ素”；选择“分类”|“边框”进行设置，如所示；2–34 “#ing的CSS规则定义”对话框单击“确定”按钮，返回到“插入DIV标签”对话框，单击“确定”按钮。删除页面中自动生成的“此处显示id＂img＂的内容”文字内容；然后在ID为img的DIV层后插入“我的世界我做主！”等相应的文字，如所示，并在其中插入一条水平线，水平线&#像素，ʯ素，左对齐。到此为止，已经将中间的内容布局设计好了，下面来设计整个网页的底部。步骤5　创建网页底部bottom选择工具栏中的“布局”，单击插入DIV标签按钮，弹出“插入DIV标签”对话框，进行如所示设置。2–25 插入DIV标签设置选择ġ单击新建CSS规则按钮，弹出“新建CSS规则”对话框，在选择器中输入“#bottom”，单击“确定”按钮，弹出“#bottom的CSS规则定义”对话框，选择“分类”|“方框”，输入宽ʯ素”，高ʯ素”，设置上边界为ʯ素”，选择“分类”|“区块”，设置文本对齐为“居中”，选择“分类”|“背景”，设置背景图像为bottom.gif。单击“确定”按钮，返回到“插入DIV标签”对话框，单击“确定”按钮。删除页面中自动生成的“此处显示id＂bottom＂的内容”文字内容。输入“版权所有©翻版必究”。至此，设计的DIV+CSS一列式布局制作完成。对照练习ġ“浮动”选项是在“分类”|“ ”中设置的。ġ一句话概括DIV+CSS布局： 。根据“素材和实例\Lj\ƚ\课堂任务1\对照练习”进行DIV+CSS的一列式布局设计，如所示。2–26 对照练习图任务小结通过本任务，初步了解了内容和形式分开的意义，学会了如何运用DIV+CSS进行一列式布局的方法，并且在网页设计过程中，可以发现网页中的内容都被各个DIV清晰地分为header，content，bottom 3个部分，并且运用不同的CSS对其修饰。总的来说，用DIV+CSS布局方法设计网页就是一个这样的过程：首先用DIV划分出一块块区域，然后用CSS控制里面内容的修饰，包括背景设置、文字大小、是否居中等。本任务完成过程如所示。2&#.2.1任务完成过程