毕业论文
计算机论文
经济论文
生物论文
数学论文
物理论文
机械论文
新闻传播论文
音乐舞蹈论文
法学论文
文学论文
材料科学
英语论文
日语论文
化学论文
自动化
管理论文
艺术论文
会计论文
土木工程
电子通信
食品科学
教学论文
医学论文
体育论文
论文下载
研究现状
任务书
开题报告
外文文献翻译
文献综述
范文
计算机算法的实践应用
摘要 用动态规划算法解决的问题的最优解,要求问题具备最优子结构性质和子问题重叠性质.动态规划将原问题化为规模更小的、相似的的子问题,并存储子问题的解以避免求解重复的子问题,从而求解原问题的算法策略.40140
毕业论文
关键词 动态规划;最优解;子问题.
一 实际问题
Tom最近忙于工作,有一大推衣服需要洗,幸运的是,他有一个既漂亮又勤快的女朋友可以帮忙.为了防止衣服相互染色,Tom把衣服按照颜色分为了几组,当然,只有洗完一种颜色的衣服才可以洗另外一种颜色的衣服.那么每一件衣服不是Tom洗就是他的女朋友洗,他们也不会同时洗一件衣服,但是可以每人洗一件同时进行.有着多年经验的Tom知道每人洗每件衣服需要的时间,那么他们洗完所有的衣服最少要多少时间呢?
二 题目分析
由题意可得,各组衣服是独立进行清洗的,那么只要把每一件衣服洗干净所需的最少时间算出来,再将他们加起来就是把脏衣服全部洗完所用的最少时间.对于每一组不同颜色的衣服,由于他们两人不会同时洗一件衣服,为了使洗完该组衣服所用的时间最少,应该尽可能让每个人分配的衣服均匀,使得他们洗衣服的时间尽可能接近,这是让他们同时洗衣服的时间最长.因此,假设用 表示其中一个人洗第 件衣服要用的时间,要求的问题就是:选择第 组衣服的一个子集,让每个人洗这些衣服所需的时间 最大,但不可以超出 .求出每个 后, 就是洗完所有衣服需要的最少时间.这是
计算机
算法中典型的物品装包问题,可以用动态规划来解决.下面先来叙述物品装包问题并讨论动态规划算法.
物品装包问题就是对 个不同待装入包中的物品,已知物品i的价值是 ,重量是 ,将他们装入承载量为 的物品装包里,要使物品装包里物品的价值最高该怎么装.
1、物品装包问题的最优子结构性质
首先用 表示物品装包问题的一个解. , 与 表示不装与要装的物品.因此物品装包问题即为如下整数规划问题.
且不妨设 是物品装包问题的一个最优解,那么 是下面相应子问题的最优解之一.
且假设上面子问题中存在优于 的解 ,有
进而有
那么 就是一个优于 的解,这和 是物品装包问题的最优解相矛盾,故物品装包问题满足最优子结构性质.
2、子问题的递归结构
对于物品装包问题的子问题
用 表示它的最优值,即物品装包承载量为 ,可选物品为 时物品装包问题的最优值. 即为给定物品装包问题的最优值. 的值可以利用最优子结构性质递归计算.当 时,这能选择物品0,若物品装包承载量小于物品0的重量 ,就不能选该物品装进物品装包,即 ,否则就将该物品装入物品装包,即 ;当 时,若物品装包承载量小于物品 的重量 ,就不能选该物品装进物品装包,即 ,否则可能选该物品装进物品装包, 的值为选择该物品和不选时的最大值,即 和 的最大值.由此可得 的递归方程如下
由此递归结构可知 的求解存在重叠子问题.
3、计算最优解
由以上分析可知物品装包问题具备最优子结构性质和子问题重叠性质,那么可以采用动态规划算法从下往上求出其最优值,给出的算法如下.
上一篇:
小学数学教材职业角色渗透研究
下一篇:
论职前数学教师的学科知识缺陷原因
微课在中学数学素质教育中的应用
中学数学教学中的模型思想与应用
凯勒流形的复结构与代数结构研究
可展曲面的判定构造及其应用
Dirichlet判别法与Abel判别法的探究
一维Schroedinger算子只有离散谱的条件
螺纹钢期货交易中几个影...
STC89C52单片机NRF24L01的无线病房呼叫系统设计
基于Joomla平台的计算机学院网站设计与开发
酵母菌发酵生产天然香料...
AES算法GPU协处理下分组加...
浅论职工思想政治工作茬...
压疮高危人群的标准化中...
从政策角度谈黑龙江對俄...
提高教育质量,构建大學生...
上海居民的社会参与研究
浅谈高校行政管理人员的...