算法:初识动态规划
发布日期:2022-03-16 03:25:38 浏览次数:26 分类:技术文章

本文共 8133 字,大约阅读时间需要 27 分钟。

0-1背包问题

对于一组不同重量、不可分割的物品,我们需要选择一些装入背包,在满足背包最大重量限制的前提下,背包中物品总重量的最大值是多少呢?

对于这个问题,可以用回溯来解决,也就是穷举搜索所有可能的装法,然后找出满足条件的最大值。不过,回溯算法的复杂度比较高,是指数级别的。那有没有什么规律,可以有效的降低时间复杂度呢?

private int maxW = Integer.MIN_VALUE; //结果放到maxW中    private int[] weight = {
2, 2, 4, 6, 3}; // 物品重量 private int n = 5; //物品个数 private int w = 9; //背包承受的最大重量 public void f(int i, int cw){
// 调用f(0, 0); if(cw == w || i == n){
// cw==w 表示装满了,i==n 表示物品都考察完了 if(cw > maxW){
maxW = cw; } return; } f(i + 1, cw); //选择不装第i个物品 if(cw + weight[i] <= w){
//装得下(剪枝) f(i + 1, cw + weight[i]); // 选择装第i个物品 } }

那怎么找出规律呢?我们来举个例子、画个图看看。我们假设背包中最大承载重量是9。我们有5个不同的物品,每个物品的重量分配是2、2、4、6、3。如果我们把这个例子的回溯求解过程,用递归树画出来,那就是下面这个样子。

在这里插入图片描述
递归树中的每个节点表示一种状态,我们用 ( i , c w ) (i, cw) (i,cw)来表示。其中,i表示将要决策第几个物品是否装入背包, c w cw cw表示当前背包中物品的总重量。比如 ( 2 , 2 ) (2,2) (22)表示我们将要决策第2个物品是否装入背包,在决策前,背包中物品的总重量是2.

从递归树中,可以发现,有些子问题的求解是重复的,比如图中 f ( 2 , 2 ) 和 f ( 3 , 4 ) f(2,2)和f(3,4) f(22)f(34)都被重复计算了两次。我们可以借助“备忘录”的解决方式,记录已经计算好的 f ( i , c w ) f(i, cw) f(i,cw)。当再次计算到重复的 f ( i , c w ) f(i, cw) f(i,cw)的时候,可以直接从备忘录中取出来用,就不用在递归计算了,这样可以避免冗余计算

private int maxW = Integer.MIN_VALUE; // 结果放到maxW中    private int[] weight = {
2, 2, 4, 6, 3}; // 物品重量 private int n = 5; // 物品个数 private int w = 9; // 背包承受的最大重量 private boolean[][] mem = new boolean[5][10]; //备忘录,默认值false public void f(int i, int cw){
//调用f(0, 0); if (cw == w || i == n) {
// cw==w 表示装满了,i==n 表示物品都考察完了 if (cw > maxW) {
maxW = cw; } return; } if(mem[i][cw]){
return; // 重复状态 } mem[i][cw] = true; // 记录(i, cw)这个状态 f(i + 1, cw); //选择不装第i个物品 if(cw + weight[i] <= w){
f(i + 1, cw + weight[i]); //选择装第i个物品 } }

这种解决方法非常好。实际上,它已经跟动态规划的执行效率基本上没有差别。但是,多一种方法就多一种解决思路,我们现在来看看动态规划是怎么做的。

  • 我们把整个求解过程分为n个阶段,每个阶段会决策一个一个物品是否放到背包中。每个物品决策(放入或者不放入背包)完之后,背包中的物品的重量就会有多种情况,也就是说,会达到多种不同的状态,对应到递归树中,就是有很多不同的节点。
  • 我们把每一层重复的状态(节点)合并,只记录不同的状态,然后基于上一层的状态集合,来推导下一层的状态集合。我们可以通过合并每一层重复的状态,这样就保证每一层不同状态的个数不会超过w个(w表示背包的承载重量)。于是,我们就成功避免了每层状态个数的指数级增长。
  • 我们用一个额外数组states[n][w+1],来记录每层可以达到的不同状态
  • 第0个物品的重量是2,要么装入背包,要么不装入背包,决策完成之后,会对应背包的两种状态,背包中物品的总重量是0或者2。我们用states[0][0]=true和state[0][2]=true表示这两种状态
  • 第1个物品的重量也是2,基于之前的背包状态,在这个物品决策完之后,不同的状态有3个,背包中物品总重量是0(0+0),2(0+2 or 2+0),4(2+2)。我们用states[1][0]=true,states[1][2]=true,states[1][4]=true表示这三种状态。
  • 以此类推,直到考察完所有的物品之后,整个states状态数组就计算好了。

整个物品的计算过程如下图,图中0表示false,1表示true。我们只需要在最后一层,找一个值为true的最接近w的值,就是背包中总重量的最大值

在这里插入图片描述

代码实现如下:

private int maxW = Integer.MIN_VALUE; // 结果放到maxW中    private int[] weight = {
2, 2, 4, 6, 3}; // 物品重量 private int n = 5; // 物品个数 private int w = 9; // 背包承受的最大重量 private boolean[][] mem = new boolean[5][10]; //备忘录,默认值false // w物品重量,n物品个数,w背包客承载重量 public int ksnapsack(int []weight, int n, int w){
boolean[][] states = new boolean[n][w+1]; //默认值为false states[0][0] = true; //第一行的数据要特殊处理,可以利用哨兵优化 states[0][weight[0]] = true; for (int i = 1; i < n; i++) {
// 动态规划状态转移 for (int j = 0; j <= w; j++) {
//不把第i个物品放入背包 if(states[i-1][j] == true){
states[i][j] = states[i-1][j]; } } for (int j = 0; j <= w-weight[i]; ++j) {
// 把第 i 个物品放入背包 if (states[i-1][j]==true) states[i][j+weight[i]] = true; } } for (int i = w; i >= 0; --i) {
// 输出结果 if (states[n-1][i] == true) return i; } return 0; }

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

动态规划时间复杂度分析:

  • 从上面代码可以看出,耗时最多的部分就是代码中的两层for循环,所以时间复杂度是O(n*w)。n表示物品个数,w表示背包可以承载的总重量
  • 从理论上来讲,指数级的时间复杂度肯定比O(n*w)高很多。举个例子,我们假设有10000个物品,重量分布在1到15000之间,背包可以承载的总重量是30000。如果我们用回溯算法解决,用具体的数值表示出时间复杂就是 2 10000 2^{10000} 210000,如果用动态规划,那就是 10000 ∗ 30000 10000*30000 1000030000,这就小多了

尽管动态规划的执行效率比较高,但是我们需要额外申请一个n乘以w+1的二维数组,对空间的消耗表较多。也可以是动态规划是一种空间换时间的解决思路。那有什么办法可以降低空间消耗吗?

实际上,我们只需要一个大小为w+1的一维数组就可以解决这个问题。动态规划状态转移的过程,都可以基于这个一维数组来操作。如下:

private int maxW = Integer.MIN_VALUE; // 结果放到maxW中    private int[] weight = {
2, 2, 4, 6, 3}; // 物品重量 private int n = 5; // 物品个数 private int w = 9; // 背包承受的最大重量 private boolean[][] mem = new boolean[5][10]; //备忘录,默认值false // w物品重量,n物品个数,w背包客承载重量 public int ksnapsack(int []items, int n, int w){
boolean[] states = new boolean[w + 1]; //默认值false states[0] = true; //第一行的数据要特殊处理,可以利用哨兵优化 states[items[0]]= true; for (int i = 1; i < n; i++) {
for (int j = w - items[i]; j >= 0 ; j--) {
//把第i个物品放入背包 // j 需要从大到小来处理。如果我们按照 j 从小到大处理的话,会出现 for 循环重复计算的问题 if(states[j]){
states[j + items[i]] = true; } } } for (int i = w; i >= 0; i--) {
// 输出结果 if(states[i]){
return i; } } return 0; }

0-1 背包问题升级版

问题:对于一组不同重量、不同价值、不可分割的物品,我们选择将某些物品装入背包,在满足背包最大重量限制的前提下,背包中可以装入物品的总价值最大是多少呢?

回溯算法解决如下:

private int maxW = Integer.MIN_VALUE; // 结果放到maxW中    private int[] weights = {
2, 2, 4, 6, 3}; // 物品的重量 private int[] values = {
3, 4, 8, 9, 6}; // 物品的价值 private int totalCount = 5; // 物品个数 private int totalWeight = 9; // 背包承受的最大重量 public void f(int i, int currWeight, int currValue){
// 调用f(0, 0, 0) if(currWeight == totalWeight || i == totalCount){
// // ccurrWeight==totalWeight 表示装满了,i== totalCount表示物品都考察完了 if(currValue > maxW){
maxW = currValue; } return; } f(i + 1, currWeight, currValue); // 选择不装第 i 个物品 if(currWeight + weights[i] <= totalWeight){
f(i + 1, currWeight + weights[i], currValue + values[i]); // 选择装第 i 个物品 } }

其递归树如下,在递归树中,每个节点表示一个状态。现在我们需要三个变量(i, currWeight,currValue)来表示一个状态,其中,i表示即将要决策第i个物品是否装入背包,currWeight表示当前背包中物品的总重量,currValue表示当前背包中物品的总价值。

在这里插入图片描述

我们发现,在递归树中,有几个节点的i和currWeight是完全相同的,比如f(2,2,4)和f(2,2,3)。在背包中物品总重量一样的情况下,f(2,2,4)这种状态对应的物品总价值更大,我们可以舍弃f(2,2,3)这种状态,只需要沿着f(2,2,4)这种决策路线继续往下决策就可以。

也就是说,对于(i,currWeight)相同的不同状态,我们只需要保留currValue值最大的那个,继续递归处理,其他状态不予考虑。

思路说完了,那么代码如何实现了。如果用回溯算法,这个问题就没法再用“备忘录”解决了。所以,我们就需要换一种思路,看看动态规划是不是更加容易解决这个问题。

我们还是把整个求解过程分为n个阶段,每个阶段会决策一个物品是否放到背包中。每个阶段决策完之后,背包中的物品的总重量以及总价值,会有多种情况,也就是会达到多种不同的状态。

我们用一个二维数组states[n][w+1],来记录每层可以达到的不同状态。不过这里数组存储的值不再是boolean类型的了,而是当前状态对应的最大总价值。我们把每一层中(i,currWeight)重复的状态(节点)合并,只记录currValue最大的那个状态,然后基于这些状态来推导下一层的状态。如下:

private int maxW = Integer.MIN_VALUE; // 结果放到maxW中    private int[] weights = {
2, 2, 4, 6, 3}; // 物品的重量 private int[] values = {
3, 4, 8, 9, 6}; // 物品的价值 private int totalCount = 5; // 物品个数 private int totalWeight = 9; // 背包承受的最大重量 public static int knapsack(int []weight, int[] value, int n, int w){
int[][] states = new int[n][w+1]; //初始化states for (int i = 0; i < n; i++) {
for (int j = 0; j < w + 1; j++) {
states[i][j] = -1; } } states[0][0] = 0; states[0][weight[0]] = value[0]; //动态规划,状态转移 for (int i = 1; i < n; i++) {
//不选择第i个物品 for (int j = 0; j <= w; j++) {
if(states[i-1][j] >= 0){
states[i][j] = states[i-1][j]; } } // 选择第i个物品 for (int j = 0; j < w - weight[i]; j++) {
if(states[i-1][j] >= 0){
int v = states[i-1][j] + value[i]; if(v > states[i][j + weight[i]]){
states[i][j + weight[i]] = v; } } } } // 找出最大值 int maxValue = -1; for (int i = 0; i <= w; i++) {
if(states[n - 1][i] > maxValue){
maxValue = states[n - 1][i]; } } return maxValue; }

时间复杂度是 O(nw),空间复杂度也是 O(nw)。

对比

  • 贪心:一条路走到黑,就一次机会,只能哪边看着顺眼走哪边
  • 回溯:一条路走到黑,无数次重来的机会,还怕我走不出来 (Snapshot View)
  • 动态规划:拥有上帝视角,手握无数平行宇宙的历史存档, 同时发展出无数个未来
    (Versioned Archive View)

转载地址:https://blog.csdn.net/zhizhengguan/article/details/122688498 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:redis面试:如何保证缓存和数据库数据的一致性?
下一篇:算法:最优子结构、无后效性和重复子问题

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月20日 18时44分55秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle里面如何查询sqlid,CSS_oracle中如何查看sql, --查询表状态:  select uo.O - phpStudy... 2019-04-21
oracle 查询中用case,oracle case when 在查询时候的用法。 2019-04-21
oracle正在运行的程序包,ORACLE PL/SQL编程详解之程序包的创建与应用 2019-04-21
php局部页面滚动,在访问另一页面后保留浏览器滚动位置 - php 2019-04-21
jmeter运行linux命令行,Jmeter在linux上运行(命令行运行Jmeter) 2019-04-21
linux服务器怎么添加站点,如何增加站点或虚拟主机及文件说明 2019-04-21
linux系统输入指令,Linux系统基础 - 基本操作命令 2019-04-21
linux设备管理命令,Linux命令(设备管理).doc 2019-04-21
linux 中文utf-8转gbk编码,Linux平台下 GBK编码转UTF-8编码 2019-04-21
linux安装软件在boot,在Linux系统上安装Spring boot应用的教程详解 2019-04-21
linux进入用户user1主目录,Linux系统命令提示符为[user1@localhost root]当前用户所在目录为( )... 2019-04-21
取消linux自动登录,linuxdeepin 如何取消自动登录啊? 2019-04-21
linux线程存储,Linux系统编程手册:线程:线程安全和每线程存储 2019-04-21
linux批处理模式,巧用linux-top的批处理模式 2019-04-21
linux信号量机制例题,第二章 信号量机制及几个经典例题 2019-04-21
linux ba 模拟,在你的 Python 游戏中模拟引力 | Linux 中国 2019-04-21
c语言表达式3649的值是,535个C语言经典实例目录.doc 2019-04-21
c语言Wndproc未定义,小弟我用c语言写了一个windows窗口,为什么有提示未定义的变量类型... 2019-04-21
c语言中malloc数组,如何在C中对malloc()数组进行一行赋值? 2019-04-21
c语言调存储过程,写留言板–调用存储过程出问题 2019-04-21