Change Dir

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

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

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

第四个动态规划问题是 最优分配问题(Optimal Allotment Problem:ALLOT),其问题描述是:有M个单位的资源,有N个人,把d个单位的资源分配给某个人有一定的成本,如何分配这些资源给这N个人,能使成本最小。这显然是一个典型的DP问题,组合优化策略,解决这个问题,首先就是要抽象DPFE动态规划方程,假设M个单位的资源,N个人,把d个单位资源分配给编号为k的人的成本计算方式为C(k,d),0≤d≤M,1≤k≤N。回想我们列DPFE方程的思路,首先要想到的就是状态,如何定义一个状态,状态总是针对总体,总共就M个单位的资源,N个人,那么我们不妨定义状态(k,m),其中k为已经分配到第k个人,m为此时所剩余的资源单位。于是把这个过程扩展,以k为分析点,此时对下一个人进行d个单位资源的分配,于是对于下一个过程,就应该是第k+1个人,总共剩余m-d个单位的资源,表示为状态(k+1,m-d)。这样,我们的DPFE也就初现端倪了:f(k,m)=min{C(k,d)+f(k+1,m-d)}。目标函数是计算f(1,M),基本条件是f(N+1,m)=0当m≥0。

我们把问题具体化,有4个苹果,要分给3个小朋友,小朋友按照1-3编号,每个小朋友拿到一定个数苹果后会哭闹一段时间(因为他们是小朋友,所以会哭闹),具体时间表如下:

C(k,d)=[

            ∞,1.0,0.8,0.4,0.0

            ∞,1.0,0.5,0.0,0.0

            ∞,1.0,0.6,0.3,0.0

           ], 1≤k≤3, 0≤d≤4

k是小朋友编号,d是分给小朋友的苹果数,可以看到,当分给小朋友0个苹果时(不分苹果),那么小朋友会无休止的哭闹,而把全部(4个)苹果全部分给一个小朋友时,小朋友不会哭闹(0时间)。那么根据这个时间,提供一个最优的分苹果方案,使得小朋友们拿到苹果后的哭闹时间最短。

那么,根据这个具体问题,我们抽象的结果就是f(1,4)=1.0+0.5+1.0=2.5,最优分布是d1=1.0,d2=0.5,d3=1.0,这样的分配方案。具体解法见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: import java.util.HashMap;
  19: import java.util.Map;
  20:  
  21: public class ALLOT {
  22:  
  23:     private static int N = 3;
  24:     private static int M = 4;
  25:     
  26:     private static final double INF=Double.MAX_VALUE;
  27:     
  28:     private static Map<Integer,Integer> choices = new HashMap<Integer,Integer>();
  29:     
  30:     private static final double [][] c = {
  31:         {INF,1.0,0.8,0.4,0.0},
  32:         {INF,1.0,0.5,0.0,0.0},
  33:         {INF,1.0,0.6,0.3,0.0}
  34:     };
  35:     
  36:     private static double cost(int k, int d) {
  37:         return c[k-1][d];
  38:     }
  39:     
  40:     public static double f(int k, int m){
  41:         if(k>N&&m>=0) return 0.0;
  42:         else{
  43:             double mm = Double.MAX_VALUE;
  44:             int dispatch = -1;
  45:             for(int d=0;d<=m;d++){
  46:                 double t = cost(k,d)+f(k+1,m-d);
  47:                 if(t<mm) {
  48:                     mm = t;
  49:                     dispatch = d;
  50:                 }
  51:             }
  52:             if(!choices.containsKey(k))
  53:                 choices.put(k, Integer.MAX_VALUE);
  54:             if(mm<choices.get(k))
  55:                 choices.put(k,dispatch);                
  56:             return mm;
  57:         }
  58:     }
  59:     /**
  60:      * @param args
  61:      */
  62:     public static void main(String[] args) {
  63:         double minCost = f(1,M);
  64:         System.out.println("min cost is : "+minCost);
  65:         System.out.print("solution is : ");
  66:         for(int i=1;i<=N;i++){            
  67:             System.out.print(choices.get(i));
  68:             if(i<N)
  69:                 System.out.print(",");
  70:         }
  71:     }
  72:  
  73: }

PS:因为考虑到这里的选择不是很长的代码,可能不影响理解DP,所以把记录选择方案的代码也加进来了。

posted on 2014-04-01 11:09 changedi 阅读(1798) 评论(4)  编辑  收藏 所属分类: 算法

评论

# re: 深入理解动态规划的一系列问题(4) 2014-04-01 21:21 施工队伍

这个问题是很值得规划的啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(4) 2014-04-02 13:00 万利锁业

期待更新啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(4) 2014-04-03 11:11 护栏

来看看那  回复  更多评论   

# re: 深入理解动态规划的一系列问题(4) 2014-04-04 10:22 柚子舍

准备好好学习下java  回复  更多评论   


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


网站导航: