-
摘要 用动态规划算法解决的问题的最优解，要求问题具备最优子结构性质和子问题重叠性质.动态规划将原问题化为规模更小的、相似的的子问题，并存储子问题的解以避免求解重复的子问题，从而求解原问题的算法策略.40140
- 上一篇：小学数学教材职业角色渗透研究
- 下一篇：论职前数学教师的学科知识缺陷原因
毕业论文关键词 动态规划；最优解；子问题.
一 实际问题
Tom最近忙于工作，有一大推衣服需要洗，幸运的是，他有一个既漂亮又勤快的女朋友可以帮忙.为了防止衣服相互染色，Tom把衣服按照颜色分为了几组，当然，只有洗完一种颜色的衣服才可以洗另外一种颜色的衣服.那么每一件衣服不是Tom洗就是他的女朋友洗，他们也不会同时洗一件衣服，但是可以每人洗一件同时进行.有着多年经验的Tom知道每人洗每件衣服需要的时间，那么他们洗完所有的衣服最少要多少时间呢？
二 题目分析
由题意可得，各组衣服是独立进行清洗的，那么只要把每一件衣服洗干净所需的最少时间算出来，再将他们加起来就是把脏衣服全部洗完所用的最少时间.对于每一组不同颜色的衣服，由于他们两人不会同时洗一件衣服，为了使洗完该组衣服所用的时间最少，应该尽可能让每个人分配的衣服均匀，使得他们洗衣服的时间尽可能接近，这是让他们同时洗衣服的时间最长.因此，假设用 表示其中一个人洗第 件衣服要用的时间，要求的问题就是：选择第 组衣服的一个子集，让每个人洗这些衣服所需的时间 最大，但不可以超出 .求出每个 后， 就是洗完所有衣服需要的最少时间.这是计算机算法中典型的物品装包问题，可以用动态规划来解决.下面先来叙述物品装包问题并讨论动态规划算法.
物品装包问题就是对 个不同待装入包中的物品，已知物品i的价值是 ，重量是 ，将他们装入承载量为 的物品装包里，要使物品装包里物品的价值最高该怎么装.
1、物品装包问题的最优子结构性质
首先用 表示物品装包问题的一个解. , 与 表示不装与要装的物品.因此物品装包问题即为如下整数规划问题.
且不妨设 是物品装包问题的一个最优解，那么 是下面相应子问题的最优解之一.
且假设上面子问题中存在优于 的解 ，有
进而有
那么 就是一个优于 的解，这和 是物品装包问题的最优解相矛盾，故物品装包问题满足最优子结构性质.
2、子问题的递归结构
对于物品装包问题的子问题
用 表示它的最优值，即物品装包承载量为 ，可选物品为 时物品装包问题的最优值. 即为给定物品装包问题的最优值. 的值可以利用最优子结构性质递归计算.当 时，这能选择物品0，若物品装包承载量小于物品0的重量 ，就不能选该物品装进物品装包，即 ，否则就将该物品装入物品装包，即 ；当 时，若物品装包承载量小于物品 的重量 ，就不能选该物品装进物品装包，即 ，否则可能选该物品装进物品装包， 的值为选择该物品和不选时的最大值，即 和 的最大值.由此可得 的递归方程如下
由此递归结构可知 的求解存在重叠子问题.
3、计算最优解
由以上分析可知物品装包问题具备最优子结构性质和子问题重叠性质，那么可以采用动态规划算法从下往上求出其最优值，给出的算法如下.