动态规划问题

应用场景

背包问题：有个背包，初始容量为4磅，现有如下物品

0 - 1背包问题，转入的商品不能重复

1）要求达到的目标为装入的背包的总价值最大，并且重量不能超过

2）要求装入物品不能重复

动态规划算法

概念

• 动态规划（DynamicProgramming）算法的核心思想是：将大问题划分成小问题进行解决，从而一步步获取最优解的处理算法
• 动态规划算法与分治法类似，其基本思想也是将带求解问题，分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
• 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步求解）
• 动态规划可以通过填表的方式来逐步推进，得到最优解

求解 0-1背包问题

• 背包问题主要指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使得物品价值最大，其中又分为01背包和完全背包（完全背包指的是：每个物品都是无限件可用）
• 这里的问题属于01背包问题，即每个物品最多放一个，而无限背包可以转回成01背包问题

主要思想

算法的主要思想，利用动态规划来解决，每次遍历到第i个物品，根据 w[i] 和 v[i] 来确定是否需要将该物品放入背包中，即对于给定的n个物品，设v[i] 、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i] [j] 表示前i个物品中能够装入容量为j的背包中的最大价值，则我们有下面的结果。

• v[i] [0] = v[0] [j] = 0
• 当w[i] > j 时：v[i] [j] = v[i - 1] [j]
• 当 j >= w[i]时：v[i] [j] = max {v[i - 1] [j] , v[i - 1] [j - w[i]] + v[i]}

思路推导图

使用填表法

解决类似的问题可以分解成一个个的小问题进行解决，假设存在背包容量大小为1,2,3,4 的各种容量的背包（分配容量的规则为最小重量的整数倍）

• 假设现在只有吉他（G），这时候不管背包容量有多大，只能放一个吉他 1500（G）
• 假设现在有 吉他 和 音箱S，那么在 0 - 3 磅的时候，只能放吉他，当为4磅的时候，能放入音箱

这个时候，就得到了公式

• v[i] [0] = v[0] [j] = 0
  • 表示第一行和第一列为0
• 当w[i] > j 时：v[i] [j] = v[i - 1] [j]
  • 当我们装入新增的商品，它的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
• 当 j >= w[i]时：v[i] [j] = max {v[i - 1] [j] , v[i] + v[i - 1] [j - w[i]] }
  • 当准备新增的商品的容量小于等于当前背包的容量，装入的方式，应该是求一个最大值
  • v[i-1] [j]：表示上一个单元格的装入的最大值
  • v[i]：表示当前商品的价值
  • v[i -1] [j - w[i]]：装入i-1商品，到剩余空间的最大值

验证公式1

• v[i] [j] = 1500
• i = 1, j = 1
• w[i] = w[1] = 1
• j >= w[i] ，满足第三个条件
• v[i] [j] = max { v[0] [1], val[1]+ v[0] [0] } = max { 0 , 1500 + 0} = 1500

验证公式2

• v[3] [4] = 3500
• i = 3, j = 4
• w[i] = w[3] = 3
• j = 4 >= w[i] ， max { v[2] [4], v[3] + v[2] [1] } = max {3000 , 2000 + 1500 } = 3500

代码实现

/**
 * 动态规划
 * 解决 0-1背包问题
 *
 * @author: 陌溪
 * @create: 2020-04-18-15:00
 */
public class DynamicProgramming {
    public static void main(String[] args) {
        // 物品的重量
        int w [] = {1, 4, 3};

        // 物品的价值
        int val [] = {1500, 3000, 2000};

        // 背包的容量
        int m = 4;

        // 物品的个数
        int n = val.length;

        // 创建二维数组  v[i][j] 表示在前i个物品中，可以装入容量为j的背包中的商品最大值
        int [][] v = new int[n+1][m+1];

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

        // 初始化第一行  和 第一列，这里在本程序中可以不去处理，因为数组默认就是0
        for(int i = 0; i<v.length; i++) {
            v[i][0] = 0;
        }
        for(int j = 0; j<v[0].length; j++) {
            v[0][j] = 0;
        }

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

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

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

        // 输出最后我们是放入的那些商品
        // 这样遍历，会把所有放入情况都用到，其实我们只需要最后的放入情况
//        for(int i = 0; i< path.length; i++) {
//            for(int j = 0; j<path[0].length; j++) {
//                if(path[i][j] == 1) {
//                    System.out.print(i + " ");
//                }
//            }
//        }

        // 求出最后的一个点
        int i = path.length -1;
        int j = path[0].length -1;
        // 从path的最后开始查找
        while (i> 0 && j>0) {
            if(path[i][j] == 1) {
                System.out.print(i + " ");
                j -= w[i-1];
            }
            // 找到一个 i需要减1
            i --;
        }
    }
}

输出结果

0 0 0 0 0 
0 1500 1500 1500 1500 
0 1500 1500 1500 3000 
0 1500 1500 2000 3500 
3 1 

你可能感兴趣的文章

Vue如何使用G2绘制图片

Docker Compose入门学习

DockerDesktop入门简介

Docker图形化工具Portainer介绍与安装

1.Docker

Docker操作系统之Alpine

如何将镜像推送到阿里云容器镜像服务

对象存储MinIO入门介绍

ElasticSearch安装与介绍

Beats入门简介