《算法图解》-9动态规划 背包问题,行程最优化

《算法图解》-9动态规划 背包问题,行程最优化本文属于《算法图解》系列。学习动态规划,这是一种解决棘手问题的方法,它将问题分成小问题,并先着手解决这些小问题。一背包问题背包问题,在可装物品有限的前提下,尽量装价值最大的物品,如果物品数量足够大,简单的暴力穷举法是不可行的O(2ⁿ),前一章介绍了《贪婪算法》就是解决如何找到近似解,这接近最优解,但可能不是最优解。如何找到最优解呢?就是动态规划算法。动态规划先解决子问题,…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

本文属于《算法图解》系列。学习动态规划,这是一种解决棘手问题的方法,它将问题分成小问题,并先着手解决这些小问题。

一 背包问题

《算法图解》-9动态规划 背包问题,行程最优化

    背包问题,在可装物品有限的前提下,尽量装价值最大的物品,如果物品数量足够大,简单的暴力穷举法是不可行的O(2ⁿ), 前一章介绍了《贪婪算法》就是解决如何找到近似解,这接近最优解,但可能不是最优解。如何找到最优解呢?就是动态规划算法。动态规划先解决子问题,再逐步解决大问题。

  每个动态规划算法都从一个网格开始,背包问题的网格如下。

《算法图解》-9动态规划 背包问题,行程最优化

  网格的各行为商品,各列为不同容量(1~4磅)的背包。所有这些列你都需要,因为它们将帮助你计算子背包的价值。网格最初是空的。你将填充其中的每个单元格,网格填满后,就找到了问题的答案。

1 吉他行

  这是第一行,只有吉他可供你选择。第一个单元格表示背包的容量为1磅。吉他的重量也是1磅,这意味着它能装入背包!因此这个单元格包含吉他,价值为1500美元。来看下一个单元格。这个单元格表示背包的容量为2磅,完全能够装下吉他!以此类推。

《算法图解》-9动态规划 背包问题,行程最优化

你知道这不是最终的解。随着算法往下执行,你将逐步修改最大价值。

2 音响行

可选的有吉他和音响。在每一行, 可选的商品都为当前行的商品以及之前各行的商品。

背包的容量为1磅,能装下音响吗?音响太重了,装不下!由于容量1磅的背包装不下音响, 因此最大价值依然是1500美元。接下来的两个单元格的情况与此相同,背包容量为4磅呢?终于能够装下音响了!

《算法图解》-9动态规划 背包问题,行程最优化

3 笔记本电脑行

下面以同样的方式处理笔记本电脑。笔记本电脑重3磅,没法将其装入容量为1磅或2磅的背 包,因此前两个单元格的最大价值还是1500美元。对于容量为3磅的背包,可选笔记本电脑而不是吉他,这样新的最大价值将为2000美元!

  《算法图解》-9动态规划 背包问题,行程最优化

对于容量为4磅的背包,情况很有趣。这是非常重要的部分。当前的最大价值为3000美元,选择笔记本电脑2000美元,还有1磅空间没用使用。根据之前计算的最大价值可知,在1磅的容量中可装入吉他,价值1500美元。因此,你需要做如下比较。

《算法图解》-9动态规划 背包问题,行程最优化

为何计算小背包可装入的商品的最大价值呢?因为余下了空间时,你可根据这些子问题的答案来确定余下的空间可装入哪些商品。笔记本电脑和吉他的总价值为3500美元,最终的网格类似于下面这样。

《算法图解》-9动态规划 背包问题,行程最优化

   你可能认为,计算最后一个单元格的价值时,我使用了不同的公式。那是因为填充之前的单元格时,我故意避开了一些复杂的因素。其实,计算每个单元格的价值时,使用的公式都相同。 这个公式如下。

《算法图解》-9动态规划 背包问题,行程最优化

你可以使用这个公式来计算每个单元格的价值,最终的网格将与前一个网格相同。现在你明 白了为何要求解子问题吧?你可以合并两个子问题的解来得到更大问题的解。

二 背包问题FAQ

2.1 再加一件商品如何

假设你还选择一件商品:iPhone

此时需要重新执行前面所做的计算吗?不需要。别忘了,动态规划 逐步计算最大价值。

《算法图解》-9动态规划 背包问题,行程最优化

沿着一列往下走时,最大价值有可能降低吗?

《算法图解》-9动态规划 背包问题,行程最优化

答案:不可能。每次迭代时,你都存储当前的最大价值。最大价值不可能比以前低!

练习:假设你还可以选择——MP3播放器,它重1磅,价值1000美元。你会选择吗?

         不会。

2.2 行的排列顺序发生变化时结果将如何

  假设你按如下顺序填充各行:音响、笔记本电脑、吉他。网格将会是什么样的?请自己动手填充这个网格,再接着往下读。

《算法图解》-9动态规划 背包问题,行程最优化

答案没有变化。也就是说,各行的排列顺序无关紧要。

2.3 可以逐列而不是逐行填充网格吗

自己动手试试吧!

这里推荐一个网站:http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html

《算法图解》-9动态规划 背包问题,行程最优化

2.4 增加一件更小的商品将如何呢

需要重新调整网格,计算的单位更新如(0.5)。可以自己动手验证下。

2.5 可以选择部分商品吗

《算法图解》-9动态规划 背包问题,行程最优化

如果想这种情况下.只装商品的一部分。如何使用动态规划来处 理这种情形呢?

答案是没法处理。使用动态规划时,要么考虑拿走整件商品,要么考虑不拿,而没法判断该不该拿走商品的一部分。

但使用贪婪算法可轻松地处理这种情况!首先,尽可能多地拿价值最高的商品;如果拿光了, 再尽可能多地拿价值次高的商品,以此类推。

2.6 旅游行程最优化

  假设你要去伦敦度假,假期两天,但你想去游览的地方很多。你没法前往每个地方游览,因此你列个单子。

《算法图解》-9动态规划 背包问题,行程最优化

这也是一个背包问题!但约束条件不是背包的容量,而是有限的时间;不是决定该装入哪些 商品,而是决定该去游览哪些名胜。请根据这个清单绘制动态规划网格。

《算法图解》-9动态规划 背包问题,行程最优化

当我在纸上画这个网格,逐个元素去填值计算的时候,边上的土豪QA妹子,应该不应这么纠结,多待两天都逛完了。可见钱能解决90%的问题。

2.7 处理相互依赖的情况

假设你还想去巴黎,因此在前述清单中又添加了几项。

《算法图解》-9动态规划 背包问题,行程最优化

去这些地方游览需要很长时间,因为你先得从伦敦前往巴黎,这需要半天时间。如果这3个地方都去玩,是不是要4.5天呢?

不是的,因为不是去每个地方都得先从伦敦到巴黎。到达巴黎后,每个地方都只需1天时间。

因此玩这3个地方需要的总时间为3.5天(半天从伦敦到巴黎,每个地方1天),而不是4.5天。

将埃菲尔铁塔加入“背包”后,卢浮宫将更“便宜”:只要1天时间,而不是1.5天。如何使 用动态规划对这种情况建模呢?

没办法建模。动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当 每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用

2.8 计算最终的解时会涉及两个以上的子背包吗

  但根据动态规划算法的设计,最多只需合并两个子背包,即根本不会涉及两个以上的子背包。不过这些子背包可能又包含子背包。

2.9 最优解可能导致背包没装满吗

完全可能,假设你选了一个3.5磅的钻石。

练习:

假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要:

《算法图解》-9动态规划 背包问题,行程最优化

我推导的结果:水+食物+相机=25

最后附上一版本Java解决背包问题。

/**
 * 
 * @author bohu83
 * @2019-06-11
 */
public class FindMaxTest {
	
	static String[] names= {"","sound","laptop","guita","phone"};
	static int[] w = {0,4, 3, 1,1 };//重量
	static int[] v = {0,3000,2000,1500,2000}; //价值
    //包按照4磅重量算
	static int[][] b = new int[5][5];


	public static void main(String[] args) {
		//一 先填充数据
        //遍历行:物品
        for (int i = 1; i <= 4; i++) {
        	//遍历列:重量
            for (int j = 1; j <= 4; j++) {
            	//装不进
                if ( j< w[i] ) {
                    b[i][j] = b[i - 1][j];                
                } else {//能装                	
                    int value1 = v[i] + b[i - 1][j - w[i]]  ; //当前商品的价值+剩余空间的价值
                    int value2 = b[i - 1][j]; // 上一单元格值
                    b[i][j] = Math.max(value1, value2);                    
                }
            }
        }
        System.out.println("value:"+b[4][4]);
        findMax(4,4);
	}
	
	/**
	 * 寻找最大值对应的物品
	 * @param i
	 * @param j
	 */
	public static void findMax(int i,int j){
		
		if(i>0){
			if(b[i][j]== b[i-1][j]){			
				System.out.println("not choose :"+names[i]+",value="+v[i]);
				findMax(i-1,j);
			}
			else if( b[i][j]==(v[i] + b[i - 1][j - w[i]]) ){			
				System.out.println("choose :"+names[i]+",value="+v[i]);
				findMax(i-1,j-w[i]);
			}
			
		}
		
	}
	
}

运行结果:

《算法图解》-9动态规划 背包问题,行程最优化

背包问题已经解决,利用动态规划解决此问题的效率即是填写此张表的效率,所以动态规划的时间效率为O(number*capacity)=O(n*c),由于用到二维数组存储子问题的解,所以动态规划的空间效率为O(n*c)。

注意下一些代码细节,例子画的网格图是为了便于理解,实际demo Java取的数组是从0开始的。所以数组的比图上的网格多加了一行,一列的0 的数组,无实际意义,纯粹为了填空格使用。还有网上有优化算法,二维数组转一维数组,只为了求值优化,但是不能找到最优组合选择的元素。感兴趣的可以试验下。

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164403.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Web移动端Fixed布局的解决方案「建议收藏」

    Web移动端Fixed布局的解决方案「建议收藏」Web移动端Fixed布局的解决方案

  • 4个基本不等式的公式高中_不等式链(高中4个基本不等式链推导)

    4个基本不等式的公式高中_不等式链(高中4个基本不等式链推导)高中数学基本不等式链如下:算术平均数(arithmeticmean),又称均值,是统计学中最基本、最常用的一种平均指标,分为简单算术平均数、加权算术平均数。它主要.几个不等式联立起来,叫做不等式组即不等式链。用大于号“>”、小于号“在不等式中,有重要作用的抄几个基本不等式,串在一起,即:当a,b>0时,2ab/(a+b)<=根号ab<=(a+b)/2<=根号[(…

  • 渗透测试工具——Metasploit[通俗易懂]

    渗透测试工具——Metasploit[通俗易懂]Metasplout简介Metasploit是一款开源的安全漏洞检测工具,同时Metasploit是免费的工具。Metasploit核心中绝大部分有Rudy实现,一小部分由汇编和C语言实现。kali中自带MetasploitMetasploit文件结构与模块路径:/usr/share/metasploit-framework/config:MSF环境配置信息,数据库配置信息 data:后渗透模块的一些工具及payload,第三方小工具集合,用户字典等数据信息 doc

  • springboot开发视频网站_springboot微服务实战

    springboot开发视频网站_springboot微服务实战​此篇是基于springboot脚手架开发的在线电影实战开发教程和完整源码;在学习JAVA中很容易遇到各种小错误大家一定要多学多练哦开发环境:Escplise/Maven3.5JAVA版本/JDK1.8数据库/Mysql5.7Navicat部分功能展示在个人中心中可以直观看到账户余额、用户优惠券、以及最近购买记录;…

  • linux rsyslogd cpu占用率高问题「建议收藏」

    linux rsyslogd cpu占用率高问题「建议收藏」最近有几次,linuxcentos7服务停了后,重启,再起一些应用后,查看top后,rsyslogdcpu占用率高问题,先说我这块怀疑导致的原因吧。原因很有可能是当前机器的系统盘挂载出现问题,或者系统盘有磁道坏了,导致,在启动某个软件时,一直在记录日志。现象top命令看下一:解决发现rsyslog可以理解为增强版的syslog,可以支持输出日志到各种数据库,使用RELP+TCP实现数据的传输,对目前的服务器服务而言,可以关闭该进程。#第一步:重启rsyslog服务,

  • mysql executereader_“c#”中“ExecuteReader”是什么意思?「建议收藏」

    mysql executereader_“c#”中“ExecuteReader”是什么意思?「建议收藏」1、MSDN上说:SendstheCommandTexttotheConnectionandbuildsaSqlDataReader.简单说,就是SqlCommand对象的方法,执行返回数据的Select语句。它的执行方法有两个:第一,ExecuteReader():针对Connection执行CommandText,并返回DbDataReader。第二,ExecuteReade…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号