当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

动态规划算法学习十例之四

发表于: 2012-09-30   作者:128kj   来源:转载   浏览:
摘要: 好文章,来自:http://blog.csdn.net/shuqin1984/archive/2010/09/02/5859223.aspx   0/1背包问题的动态规划法求解,前人之述备矣,这里所做的工作,不过是自己根据理解实现了一遍,主要目的还是锻炼思维和编程能力,同时,也是为了增进对动态规划法机制的理解和掌握。    值得提及的一个问题是,在用
好文章,来自:http://blog.csdn.net/shuqin1984/archive/2010/09/02/5859223.aspx


  0/1背包问题的动态规划法求解,前人之述备矣,这里所做的工作,不过是自己根据理解实现了一遍,主要目的还是锻炼思维和编程能力,同时,也是为了增进对动态规划法机制的理解和掌握。

   值得提及的一个问题是,在用 JAVA 实现时, 是按算法模型建模,还是用对象模型建模呢? 如果用算法模型,那么背包的值、重量就直接存入二个数组里;如果用对象模型,则要对背包以及背包问题进行对象建模。思来想去,还是采用了对象模型,尽管心里感觉算法模型似乎更好一些。有时确实就是这样,对象模型虽然现在很主流,但也不是万能的,采用其它的模型和视角,或许可以得到更好的解法。

public class Knapsack {
 
       /** 背包重量  */
       private int weight;
 
        /** 背包物品价值  */
        private int value;

 
        /**
          * 构造器
          */
        public Knapsack(int weight, int value) {
             this.value = value;
             this.weight = weight;
        }

 
        public int getWeight() {
             return weight;
        }

 
        public void setWeight(int weight) {
             this.weight = weight;
        }
 
        public int getValue() {
            return value;
        }

 
       public void setValue(int value) {
           this.value = value;
       }
 
       public String toString() {
            return "[weight: " + weight + " " + "value: " + value + "]";  
       }

}

import java.util.ArrayList;

/**
 * 求解背包问题:
 * 给定 n 个背包,其重量分别为 w1,w2,……,wn, 价值分别为 v1,v2,……,vn
 * 要放入总承重为 totalWeight 的箱子中, 
 * 求可放入箱子的背包价值总和的最大值。
 * 
 * NOTE: 使用动态规划法求解 背包问题
 * 设 前 n 个背包,总承重为 j 的最优值为 v[n,j], 最优解背包组成为 b[n];
 * 求解最优值:
 * 1. 若 j < wn, 则 : v[n,j] = v[n-1,j];
 * 2. 若  j >= wn, 则:v[n,j] = max{v[n-1,j], vn + v[n-1,j-wn]}。
 */

public class KnapsackProblem {
 
         /** 指定背包 */
         private Knapsack[] bags;
 
         /** 总承重  */
         private int totalWeight;
 
          /** 给定背包数量  */
          private int n;
 
          /** 前 n 个背包,总承重为 totalWeight 的最优值矩阵  */
          private int[][] bestValues;
 
          /** 前 n 个背包,总承重为 totalWeight 的最优值 */
          private int bestValue;
 
          /** 前 n 个背包,总承重为 totalWeight 的最优解的物品组成 */
          private ArrayList<Knapsack> bestSolution;
 

          public KnapsackProblem(Knapsack[] bags, int totalWeight, int n) {
                  this.bags = bags;
                  this.totalWeight = totalWeight;
                  this.n = n;
                  if (bestValues == null) {
                         bestValues = new int[n+1][totalWeight+1];
                  }
                  if (bestSolution == null)
                         bestSolution = new ArrayList<Knapsack>();
          }
 
          /**
           * 求解前 n 个背包、给定总承重为 totalWeight 下的背包问题
           * 
           */
   public void solution() {
  
       System.out.println("给定背包:");
       for(Knapsack b: bags) {
              System.out.println(b);
       }
        System.out.println("给定总承重: " + totalWeight);
  
         // 求解最优值
   for (int j = 0; j <= totalWeight; j++) {
      for (int i = 0; i <= n; i++) {
   
         if (i == 0 || j == 0) {
            bestValues[i][j] = 0;
          } 
          else 
         {
          // 如果第 i 个背包重量大于总承重,则最优解存在于前 i-1 个背包中,
            // 注意:第 i 个背包是 bags[i-1]
           if (j < bags[i-1].getWeight()) {
               bestValues[i][j] = bestValues[i-1][j];
           } 
           else 
           {
        // 如果第 i 个背包不大于总承重,则最优解要么是包含第 i 个背包的最优解,
         // 要么是不包含第 i 个背包的最优解, 取两者最大值,这里采用了分类讨论法
        // 第 i 个背包的重量 iweight 和价值 ivalue
          int iweight = bags[i-1].getWeight();
          int ivalue = bags[i-1].getValue();
          bestValues[i][j] = 
  Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);  
           } // else
          } //else   
        } //for
      } //for
  
 // 求解背包组成
     int tempWeight = totalWeight;
     for (int i=n; i >= 1; i--) {
     if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) {
          bestSolution.add(bags[i-1]);
          tempWeight = totalWeight - bags[i-1].getWeight();
       }
      }
    }
 
        /**
         * 获得前  n 个背包, 总承重为 totalWeight 的背包问题的最优解值
           * 调用条件: 必须先调用 solution 方法
           * 
           */
          public int getBestValue() {
  
                    bestValue = bestValues[n][totalWeight];
                    return bestValue;
          }
 
         /**
          * 获得前  n 个背包, 总承重为 totalWeight 的背包问题的最优解值矩阵
            * 调用条件: 必须先调用 solution 方法
            * 
            */
          public int[][] getBestValues() {
     
                  return bestValues;
          }
    
          /**
           * 获得前  n 个背包, 总承重为 totalWeight 的背包问题的最优解值矩阵
            * 调用条件: 必须先调用 solution 方法
            * 
            */
           public ArrayList<Knapsack> getBestSolution() {
                  return bestSolution;
           }

 
}
public class TestKnapsack {
 
    public static void main(String[] args) {
  
        Knapsack[] bags = new Knapsack[] {
              new Knapsack(2,12), new Knapsack(1,10),
              new Knapsack(3,20), new Knapsack(2,15)
        };
         int totalWeight = 5;
         int n = bags.length;
       KnapsackProblem kp = new KnapsackProblem(bags, totalWeight, n);
  
          kp.solution();
          System.out.println(" -------- 该背包问题实例的解: --------- ");
          System.out.println("最优值:" + kp.getBestValue()); 
          System.out.println("最优解【选取的背包】: ");
          System.out.println(kp.getBestSolution());
          System.out.println("最优值矩阵:");
          int[][] bestValues = kp.getBestValues();
          for (int i=0; i < bestValues.length; i++) {
                  for (int j=0; j < bestValues[i].length; j++) {
                     System.out.printf("%-5d", bestValues[i][j]);
                  }
                  System.out.println();
          }
     }

}



给定背包:
[weight: 2 value: 12]
[weight: 1 value: 10]
[weight: 3 value: 20]
[weight: 2 value: 15]
给定总承重: 5
-------- 该背包问题实例的解: ---------
最优值:37
最优解【选取的背包】:
[[weight: 2 value: 15], [weight: 1 value: 10], [weight: 2 value: 12]]
最优值矩阵:
0    0    0    0    0    0
0    0    12   12   12   12
0    10   12   22   22   22
0    10   12   22   30   32
0    10   15   25   30   37

下载源码

动态规划算法学习十例之四

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1、最优二叉搜索树的动态规则算法 二叉搜索树是一颗满足如下条件的树: 1.每个节点包含一个键值 2.每
一、数组的最大子段和问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列
凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1,v2,… ,v8},任意两顶点间的线段的权重由矩阵
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解
例一:计算二项式系数: 在排列组合里面,我们有下面的式子(很容易用组合的定义来证明): 这个式
例一: 给出N台电脑和K辆卡车,要求每辆卡车至少放一台电脑。问共有多少种放法运走这些电脑? 数据范
1,什么是动态规划(DP)? 非常重要!,不要认为概念不重要,理解的深刻,你才知道对于什么样的问
前言 最近帮同学写一个程序,给出100多个金额,用数组表示为money[1-100],再给出一个数额SUM。如果
动态规划方法是对解最优问题的一种方法,一种途径,并不是一种特殊的算法。 执行步骤: 1. 找出最优
使用SQL管理用户和安全: 管理数据库用户管理过程:创建用户,create user user_id identified by [
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号