# Change Dir

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

• 积分 - 367410
• 排名 - 139

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

   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.Arrays;
  19:
  20: public class ARC {
  21:
  22:     private static double[] weight = { 2, 3, 1, 4 };
  23:
  24:     private static int N = weight.length - 1;
  25:
  26:     private static double sum(int p, int q) {
  27:         double result = 0.0;
  28:         for (int k = p; k <= q; k++) {
  29:             result += weight[k];
  30:         }
  31:         return result;
  32:     }
  33:
  34:     public static double f(int firstIndex, int lastIndex){
  35:         if(firstIndex == lastIndex)
  36:             return 0.0;
  37:         double min = Double.MAX_VALUE;
  38:         for(int d=firstIndex;d<lastIndex;d++){
  39:             double t = f(firstIndex,d) + f(d+1,lastIndex) + sum(firstIndex,lastIndex);
  40:             if(t<min)
  41:                 min = t;
  42:         }
  43:         return min;
  44:     }
  45:
  46:     /**
  47:      * @param args
  48:      */
  49:     public static void main(String[] args) {
  50:         Arrays.sort(weight);
  51:         System.out.println(f(0,N));
  52:     }
  53:
  54: }

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

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