Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

深入理解动态规划的一系列问题(9)

      今天介绍的动态规划问题是个有意思的问题,名字叫做Covering,问题描述如下:有k朵不同尺寸的花,现在天气变凉,为了防止花被霜冻,现在需要生产不超过n种尺寸的遮罩来保护这些花,条件是n≤k,并且允许大尺寸的遮罩保护小尺寸的花朵,对应生产k种不同尺寸的遮罩,有不同的生产成本,目标就是给出最低成本及方案。举个具体例子来说明这个问题,假设k=10,即有10朵大小不一的花,将这些花按尺寸从小到大排序并编号,为0~k-1,生产对应尺寸遮罩的成本为c={1,4,5,7,8,12,13,18,19,21},n=3,即现有条件只允许生产3种尺寸的遮罩,那么最优方案是什么,最低成本是多少?

      因为限制了n=3,也就是需要我们在c这个成本序列里添加两个分界把这个序列分为3个子序列,然后每部分按照最大的那个尺寸去加和,然后最后加和3个子序列和来确定成本。如果我们把分界定为3和6(第3个和第6个,指定下标),那么需要生产的其实是c[3]=7和c[6]=13以及c[9]=21的遮罩,而总和C=7*size(0~3)+13*size(4~6)+21*size(7~9)=7*4+13*3+21*3=130。而要想求得最优方案和最低成本,我们明显需要划分出所有可能的组合而求最小值,这典型的DP求解。

      DP求解的第一步就是定义状态,这个在之前也说过无数次了,状态定义是状态转移方程的基础。那么这个问题因为涉及到遮罩和花朵两种对象,所以我们自然的想到用(j,l)来定义状态,其中j是有多少种遮罩需要确定,l是尚未被确定遮罩的花朵中的最大尺寸的花朵(位置下标)。通过这个定义,可以知道目标函数是求f(n,k-1),而基础条件是f(1,l)=(l+1)*c[l],当j=1时。DPFE为f(j,l)=min {(l-k)*c[l]+f(j-1,l-k)}当j>1时,且k∈(j-2,…,l-1)。

      综上,最优分隔应该是4,6和9,显然9是必须在这个分隔组里的。那么最低成本C=8*size(0~4)+13*size(5~6)+21*size(7~9)=8*5+13*2+21*3=129。

source code:

   1: /*
   2:  * Copyright (C) 2013 changedi
   3:  *
   4:  * Licensed under the Apache License, Version 2.0 (the "License");
   5:  * you may not use this file except in compliance with the License.
   6:  * You may obtain a copy of the License at
   7:  *
   8:  * http://www.apache.org/licenses/LICENSE-2.0
   9:  *
  10:  * Unless required by applicable law or agreed to in writing, software
  11:  * distributed under the License is distributed on an "AS IS" BASIS,
  12:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13:  * See the License for the specific language governing permissions and
  14:  * limitations under the License.
  15:  */
  16: package com.jybat.dp;
  17:  
  18: //optimal COVering problem
  19: public class COV {
  20:     // cost of cover sizes 0,1,..,9 in dollar
  21:     private static int[] cost = { 1, 4, 5, 7, 8, 12, 13, 18, 19, 21 };
  22:  
  23:     public static double f(int numberOfCoverSizes, int largestSize) {
  24:         //numberOfCoverSizes denotes the stage number in this problem        
  25:         if (numberOfCoverSizes == 1)
  26:             return (largestSize + 1) * cost[largestSize];
  27:         double min = Double.MAX_VALUE;
  28:         for (int nextCoverSize = numberOfCoverSizes - 2; nextCoverSize <= largestSize - 1; nextCoverSize++) {
  29:             double t = (largestSize - nextCoverSize) * cost[largestSize]
  30:                     + f(numberOfCoverSizes - 1, nextCoverSize);
  31:             if (t < min)
  32:                 min = t;
  33:         }
  34:         return min;
  35:     }
  36:  
  37:     /**
  38:      * @param args
  39:      */
  40:     public static void main(String[] args) {
  41:         System.out.println(f(3, 9));
  42:     }
  43:  
  44: }


posted on 2014-05-06 15:55 changedi 阅读(1493) 评论(0)  编辑  收藏 所属分类: 算法


只有注册用户登录后才能发表评论。


网站导航: