Change Dir

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

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

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

今天要说的 是0/1背包问题,问题非常经典,即:给定一个袋子,容量为c,c∈N,同时有n个球A={a0,a1,…a(n-1)},每个球有一自己的价值v(ai),同时有一定的重量w(ai),目标就是尽可能的装球使得总价值最高,同时重量不能超出袋子的容量c。所以形式化表示这个问题即,对于Σwixi<=c,求最大max z=Σvixi。这个问题可以被看做一个多阶段决策问题,对于每个ai,都要做决策xi来判断是否要装ai,阶段标示即n个物体A的下标,那么动态规划方程如下:f(i,w)= 0 if i=-1 and 0≤w≤c,f(i,w)=-∞ if i=-1 and w<0,f(i,w)=max {xivi+f(i-1,w-xiwi)} if i≥0。目标自然是计算f(n-1,c)咯。其实现在理解01背包,典型的思路就是能阶段性考虑,递归求解。不妨设c=22,n=3,v={25,24,15},w={18,15,10}。那么结论就是只选择第一个球,最终切价值最高~~当然这个例子可能特殊了点,但是从公式上推理,我们知道这个递归方程是正确的。

源码如下:

   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.HashSet;
  19: import java.util.Set;
  20:  
  21: /**
  22:  * Knapsack01Problem.
  23:  * 
  24:  * @author zunyuan.jy
  25:  * 
  26:  * @since 2014年6月13日
  27:  */
  28: public class KS01 {
  29:  
  30:     private static int knapsackCapacity = 22;
  31:     private static int[] value = { 25, 24, 15 };
  32:     private static int[] weight = { 18, 15, 10 };
  33:     private static int n = value.length; // number of objects n=3
  34:     private static int highestIndex = n - 1; // items are indexed
  35:  
  36:     // from 0 through n-1
  37:  
  38:     private static Set<Integer> calculateDecisionSet(int objInd, int w) {
  39:         Set<Integer> decSet = new HashSet<Integer>();
  40:         decSet.add(new Integer(0)); // decision to not take object
  41:         // is always feasible
  42:         if (w >= weight[objInd]) { // check if there is enough space
  43:             // to take object
  44:             decSet.add(new Integer(1));
  45:         }
  46:         return decSet;
  47:     }
  48:  
  49:     public static double f(int currentObejctIndex, int weightToGive) {
  50:         if (currentObejctIndex == -1)
  51:             return 0.0;
  52:         Set<Integer> decisionSet = calculateDecisionSet(currentObejctIndex,
  53:                 weightToGive);
  54:         double max = 0.0;
  55:         for (int d : decisionSet) {
  56:             double tmp = d
  57:                     * value[currentObejctIndex]
  58:                     + f(currentObejctIndex - 1, weightToGive - d
  59:                             * weight[currentObejctIndex]);
  60:             if (tmp > max)
  61:                 max = tmp;
  62:         }
  63:         return max;
  64:     }
  65:  
  66:     /**
  67:      * @param args
  68:      */
  69:     public static void main(String[] args) {
  70:         System.out.println(KS01.f(2, 22));
  71:     }
  72:  
  73: }


posted on 2014-06-16 13:02 changedi 阅读(2323) 评论(6)  编辑  收藏 所属分类: 算法

评论

# re: 深入理解动态规划的一系列问题(15) 2014-06-16 14:25 IT前线

很想继续看完,太难呀

http://www.itqx.net  回复  更多评论   

# re: 深入理解动态规划的一系列问题(15) 2014-06-22 09:58 手赚网-手机赚钱软件排行,手机赚钱平台,网络赚钱http://www.szapk.cn

轻松赚:http://www.szapk.cn/ruanjianzhongxin/30.html  回复  更多评论   

# re: 深入理解动态规划的一系列问题(15) 2014-06-27 17:22 e

e  回复  更多评论   

# re: 深入理解动态规划的一系列问题(15) 2014-06-27 17:22 e

真的可以评论啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(15)[未登录] 2014-06-27 17:23 a

真的可以评论啊啊啊!  回复  更多评论   

# re: 深入理解动态规划的一系列问题(15) 2014-07-15 02:29 自媒体

有料  回复  更多评论   


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


网站导航: