# Change Dir

• 随笔 - 222
• 文章 - 0
• 评论 - 182
• 引用 - 0

• 积分 - 414591
• 排名 - 133

## 深入理解动态规划的一系列问题（4）

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时间）。那么根据这个时间，提供一个最优的分苹果方案，使得小朋友们拿到苹果后的哭闹时间最短。

   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 阅读(1793) 评论(4)  编辑  收藏 所属分类: 算法

### 评论

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

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: