欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划算法

程序员文章站 2022-05-21 19:58:00
...

动态规划算法

数据结构整理目录>>>

基本介绍

动态规划算法

基本步骤

  1. 动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步取得最优解的处理算法
  2. 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解
  3. 与分治法不同的是,适用于动态规划求解得到的问题,经分解得到的子问题 往往不是相互独立的。(即下一个阶段的求解是建立在上一个阶段的解的基础上,进行进一步求解)
  4. 动态规划问题可以通过填表的方式来逐步推进,得到最优解

实际案例-背包问题

动态规划算法

思路分析

每次遍历到第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i],w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[ i] [ j]表示在前i个物品中能够装入容量为j的背包中的最大价值,则我们有下面的结果:

  1. v[i] [0]=v[0] [j] =0 //表示填入表第一行和第一列是0(把i个商品装入到0磅背包中,把0个商品装入到j磅背包中的价值 均为0)

  2. 当w[i]>j时;v[i] [j] = v[i-1] [j] //当准备新增商品的容量大于当前背包的容量时,就直接使用上一个单元格的装入策略

  3. 当j>=w[i]时;v[i] [j] = max{v[i-1] [j],v[i-1] [j-w[i]]+v[i]} //当准备加入的新增的商品的容量小于当前背包的容量;

    装入的策略: v[i-1] [j] 上一个单元格的装入最大值

    ​ v[i]表示当前商品的价值

    ​ v[i-1] [j-w[i]] 表示 (装入i-1个商品到剩余空间j-w[i](把当前商品扣除之后的一个子问题)的最大值(使用到递归思想)

动态规划算法

动态规划算法

代码

package L十大算法.Dynamic;

/**
 * @Author Zhou  jian
 * @Date 2020 ${month}  2020/1/14 0014  15:19
 * 背包问题
 */
public class KnapsackProblem {

    public static void main(String[] args) {

        int[]  w = {1,4,3};//物品的重量
        int[]  val ={1500,3000,2000};//物品的价值。这里de val[i]就是v[i]
        int m = 4;//背包的容量
        int n = val.length;//物品的个数

        //创建二维数组
        //v[i][j]:在前一个
        int[][]  v = new int[n+1][m+1]; //因为有一行为0,一列为0

        //为了记录放入商品的情况,我们定义一个二维数组
        int[][] path = new int[n+1][m+1];

        //初始化第一行和第一列,在本程序中,可以不处理
        for(int i=0;i<v.length;i++){
            v[i][0]=0;//将第一列设置为0
        }
        for(int i=0;i<v[0].length;i++){
            v[0][i]=0;//将第一行设置为0
        }

        //输出v
        for(int i=0;i<v.length;i++){
            for (int j=0;j<v[i].length;j++){
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }

        //根据前面得到的公式进行动态规划处理
        for(int i=1;i<v.length;i++){//不处理第一行
            for(int j=1;j<v[0].length;j++){//不处理第一列
                //公式//因为我们的程序 i是从1开始的 因此原来公式中的w[i]要修改成w[i-1]
                if(w[i-1]>j){
                    v[i][j] = v[i-1][j];
                }else{
                    //v[i] [j] = max{v[i-1] [j],v[i-1] [j-w[i]]+v[i]}
                    //说明我们的i是从1开始的所以公式需要调整成
//                    v[i][j]= Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);

                    //为了记录商品存放到背包的情况,我们不能简单的使用上面的公式,需要使用if...elese来体现公式
                    if(v[i-1][j]>=val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=v[i-1][j];
                    }else{
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        //把当前情况记录
                        path[i][j]=1;
                    }
                }

            }
        }

        //输出v
        for(int i=0;i<v.length;i++){
            for (int j=0;j<v[i].length;j++){
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }

        //输出最后我们放入哪些商品
        //遍历path,这样输出会把所有的放入情况都得到,其实我们需要最后放入
//        for(int i=0;i<path.length;i++){
//            for(int j=0;j<path[i].length;j++){
//                if(path[i][j]==1)
//                System.out.printf("第%d个商品放入到背包\n",i);
//            }
//        }



        int i = path.length-1;//行的最大下标
        int j = path[0].length-1;//列的最大下标
        while(i>0 && j>0){  //从path的最后开始找
            if(path[i][j]==1){
                System.out.printf("第%d个商品放入到背包\n",i);
                j -=w[i-1];
            }
            i--;
        }


    }

}