专栏首页算法半岛数据结构与算法-动态规划(一)

数据结构与算法-动态规划(一)

动态规划思想

动态规划的主要思想:将问题分解为多个阶段,每个阶段对应一个决策。记录每一个阶段可达的状态集合(去掉重复的),然后通过当前阶段的状态集合来推导下一个阶段的状态集合,动态地往前推进。

简单0-1背包问题

动态规划最经典问题:0-1背包问题,但是经典的0-1背包问题给每个物品赋予两种属性(重量、价值),往往初次看此问题时难度较大。为了便于理解,先从经典的0-1背包问题提取一种属性进行分析(重量),题目如下:

简单0-1背包问题:已知n个物品,每种物品对应有一个重量 weight,给定一个背包可以装入物品的最大重量为 maxWeight,求满足最大重量限制的情况下,背包中物品总重量的最大值是多少?

首先通过一个例子来分析简单0-1背包问题。假设总共有5种物品,即 n=5,每个物品的重量为 weights=[2,2,4,6,3],最大重量 maxWeight=9。如下表所示,表中的行表示第几个物品,表中的列表示物品的重量,记为 curWeight,由于背包的最大重量 maxWeight=9,因此,该背包总共有0~9种重量的可能。

> 初始状态如下表所示:

【简单0-1背包问题初始状态】

> 当第0号物品决策完之后,即将0号物品不放入背包或将0号物品放入背包,如果不放入背包,即 curWeight=0,如果放入背包,即 curWeight=2,改变表中的对应状态:

【简单0-1背包问题第0号物品决策后的状态】

> 当第1号物品决策完之后,即将1号物品不放入背包或将1号物品放入背包,如果不放入背包,基于 n=0时的状态集合,该背包中的重量有两种可能,即 curWeight=0curWeight=2,如果放入背包,基于 n=0时的状态集合,该背包中的重量有两种可能,即 curWeight=2curWight=4,综上,1号物品决策完之后,背包中的重量总共有三种可能,即 curWeight=0curWeight=2curWight=4。改变表中的对应状态:

【简单0-1背包问题第1号物品决策后的状态】

> 当第2号物品决策完之后,表中状态如下所示:

【简单0-1背包问题第2号物品决策后的状态】

> 当第3号物品决策完之后,表中状态如下所示:

【简单0-1背包问题第3号物品决策后的状态】

> 当第4号物品决策完之后,表中状态如下所示:

【简单0-1背包问题第4号物品决策后的状态】

根据题目中最大重量 maxWeight=9和上表可知,当前背包下物品总重量的最大值为9。

通过上述分析,再看看将上述过程转化为 java代码,如下所示:

/** * 背包中物品总重量的最大值 * @param weight 每个物品的重量数组 * @param n 物品的个数 * @param maxWight 背包可承受的最大重量 * @return 背包中物品总重量的最大值 */public int getMaxWeightInPackage(int[] weight, int n, int maxWight){    int res = 0;    Boolean[][] state = new Boolean[n][maxWight+1]; // 先申请状态数组,即上面的表格的初始化状态
    // 对第0行进行特殊处理,手动标记    state[0][0] = true;             //  将第0号物品不放入背包    state[0][weight[0]] = true;     // 将第0号物品放入背包
    // 依次对剩下的物品进行决策    for (int i=1; i<n; i++){        // 将第i号物品不放入背包        for (int j=0; j<=maxWight; j++){            if ( state[i-1][j] != null && state[i-1][j] == true){                state[i][j] = state[i-1][j];            }        }
        // 将第i号物品放入背包        for (int j=0; j<= (maxWight-weight[i]); j++){            if(state[i-1][j] != null && state[i-1][j] == true)                state[i][j+weight[i]] = true;        }    }
    // 在最后一行从后向前遍历    for (int i=maxWight; i>=0; i--){        if(state[n-1][i] != null && state[n-1][i] == true){            res = i;            break;        }    }    return res;}

从上述实例可知,对于每个物品都有两种决策方案,要么放入背包,要么不放入背包。将整个过程分解成n个部分,对于每个部分都有两种决策方案,当每个物品决策完之后(放入背包或不放入背包)背包中的重量有多种情况,也就是说达到多种不同的情况。把每一层重复的状态合并,只记录不同的状态,然后基于上一层的状态集合,来推导下一层的状态集合。当所有部分决策完之后,即可得到最终的状态集合,从状态集合中可以得到该背包中最大的重量。

实际上,这就是动态规划解决问题的基本思路。将问题分解为多个阶段,每个阶段对应一个决策。我们记录每一个阶段可达的状态集合(去掉重复的部分),然后通过当前的状态集合来推到下一阶段的状态集合,动态地往前推进。

从上述代码可知,该问题的时间复杂度为 O(n*weight),其中 n为物品的个数, maxWeight为背包可承载的最大重量,该问题的空间复杂度为 O(n*weight),其中 n为物品的个数, maxWeight为背包可承载的最大重量。

优化:事实上,只需要申请 weight+1的一维数组即可解决这个问题。 java代码如下:

public int getMaxWeightInPackage2(int[] weight, int n, int maxWight) {    int res = 0;    Boolean[] state = new Boolean[maxWight+1]; // 先申请状态数组
    // 对第0行进行特殊处理,手动标记    state[0] = true;             //  将第0号物品不放入背包    state[weight[0]] = true;     // 将第0号武平放入背包
    // 依次对剩下的物品进行决策    for (int i = 1; i < n; i++) {        for (int j=maxWight-weight[i]; j>=0; j--){  // 把第i个物品放入背包中            if (state[j] != null && state[j] == true)                state[j+weight[i]] = true;        }    }
    // 在最后一行从后向前遍历    for (int i=maxWight; i>=0; i--){        if(state[i] != null && state[i] == true){            res = i;            break;        }    }
    return res;}    

简单0-1背包问题问题分析完成后,接下来将价值属性也添加进入,升级为高级0-1背包问题,请查阅《数据结构与算法-动态规划(二)》。

本文分享自微信公众号 - 算法半岛(jacob2359),作者:算法半岛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法-动态规划(二)

    高级0-1背包问题:已知n个物品,每种物品对应有重量 weight和价值 value两个属性,给定一个背包可以装入物品的最大重量为 maxWeight,求满足...

    用户3470542
  • LeetCode-1 两数之和

    给定一个整数数组 nums和一个目标值 target,请你在该数组中找出和为目标值的那 两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个...

    用户3470542
  • Hash表(一)——Hash函数

    Hash表也叫 散列表,具有像数组那样根据随机访问的特性,可以根据 key来获得 value。

    用户3470542
  • ARP-基础-扫描-攻击-防范

    ARP(Address Resolution Protocol)地址解析协议,将已知IP地址转换为MAC地址,由RFC820定义 ARP协议在OSI模型中处于数...

    糖果
  • 动态规划算法秘籍

    动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和...

    rainchxy
  • ​带你深入理解Java内存模型JMM

    在并发编程中,我们需要处理两个关键问题:线程之间如何通信及线程之间如何同步(这里的线程是指并发执行的活动实体)。通信是指线程之间以何种机制来交换信息。在命令式编...

    Java技术江湖
  • 【常用配置】Hadoop-2.6.5在Ubuntu14.04下的伪分布式配置

    core-site.xml <?xml version="1.0" encoding="UTF-8"?> <?xml-stylesheet type="text...

    用户1148394
  • matlab GUI基础5

    高级文件I/O——图像和视频文件 函数说明imread说明图像文件imwrite写入图像文件imfinfo获取图像文件的信息imshow显示图像imformat...

    anytao
  • logstash之input配置redis类型详解

    用途 监控redis数据 配置示例 input {     redis {         data_type => "list"         key =>...

    苦咖啡
  • 微软研究院推出支持PowerBI的作图大杀器

    微软在Ignite2018关于PowerBI的演示中使用了一个很猛的自定义可视化,先来看看效果:

    BI佐罗

扫码关注云+社区

领取腾讯云代金券