【学习草稿】背包问题

一、01背包问题 图解+详细解析 (转载)
https://blog.csdn.net/qq_37767455/article/details/99086678

:Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积,定义V(i,j):当前背包容量 j,前 i 个物品最佳组合对应的价值
大概看懂,并根据公式手填了一下表格

最优性原理的基本思想是:一个问题的最优解包含了其子问题的最优解。换句话说,一个问题的最优解可以通过其子问题的最优解递推得到。

最优性原理的应用条件是问题具有最优子结构,即一个问题的最优解可以通过其子问题的最优解递推得到。如果一个问题不具有最优子结构,则不能使用动态规划算法求解。
疑问:原理?为什么是这样的公式呢?

二、【动态规划】01背包问题(通俗易懂,超基础讲解)
https://blog.csdn.net/qq_38410730/article/details/81667885

【好的理解评论?】
我认为那个对于面对一个商品的可能性的描述应该是这样:
1.包的总容量比商品体积小,即使不装其他商品也不可能装得下该商品,此时价值与前i-1个商品的价值一样,即v[i][j]=v[i-1][j];
2.包的总容量大于等于该商品,但若拿出其它商品来获得容量装该商品,此时价值不一定大于前i-1个商品的最大价值,所以在装与不装该商品之间选定一个,即V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}
【评论】
j<w(i) 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)}
各位老师,我对这个迭代公式的理解:V(i,j)是指让你最多装j容量的情况下,前i个商品的最大价值,其实是根据题目最终的容量来定义的,也就是让你最多装8容量,求前4个商品的最大价值。那么可以这么理解,第i个商品装不下,那只能装前i-1个商品,V(i,j)就等于V(i-1,j);第i个商品装的下,装和不装两种情况的最优价值是不一样的,取一个最大值,V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)},V(i-1,j-w(i))+v(i)这个表示我装第i个商品,那么前i-1个商品只能让你最多装j-w(i)的情况下的最大价值。
【】
在状态表V(i,j)中 “j” 就是表示当前背包的总容量。并且在状态转移方程中 V(i-1,j-w(i)) 也并不是说当前背包容量减少了w(i),而是说为了在当前容量为 j 的背包中装入容量为w(i)的物品,所以往前寻找背包容量为 j-w(i) 的状态下的最优值 V(i-1,j-w(i)),这也是状态转移方程的意义所在。
【】
V(0,j):当前背包容量为j,前0个物品最佳组合对应的价值,肯定是0啊(没放东西);
V(i,0):当前背包容量为0,前j个物品最佳组合对应的价值,肯定是0啊(放不进去)。
【???】
动态规划推导不出来递推关系式怎么搞?-- 多看看一些动态规划的例子,感觉一下,这只能多做些题目,就有思路了。
【】
我在手动填表格的时候才真正理解V(i-1,j-w(i))的意思。例如V(4,8),背包容量为8的时候,是否塞入第4个商品的最优V。塞入第4个商品的解为:因为第4个商品的W是5,先在背包腾出5的空间(既定要放进第4个商品),也就是空间为3的最优解加上第4个商品的价值v4。

三、动态规划 原理

1、动态规划中的无后效性(Principle of Optimality)指的是,一个问题的最优解包含了其子问题的最优解,且子问题的最优解不受后续决策的影响。换句话说,一个问题的最优解可以通过其子问题的最优解递推得到,而且子问题的最优解不受后续决策的影响。

这个性质是动态规划算法的核心原理之一,也是其能够高效求解具有最优子结构问题的关键。在动态规划算法中,问题被分解成一系列子问题,并通过递推的方式求解子问题的最优解。在求解过程中,使用了一些启发式规则和策略来指导搜索过程,从而加速搜索并提高搜索结果的质量。同时,通过保存已经求解的子问题的结果,避免了重复计算,提高了算法的效率。

需要注意的是,无后效性是动态规划算法的基本性质之一,但并不是所有问题都具有无后效性。如果一个问题不具有无后效性,则不能使用动态规划算法求解。因此,在使用动态规划算法时,需要先确定问题是否具有无后效性,以避免错误的求解方法。
2、什么是无后效性?
https://blog.csdn.net/qq_30137611/article/details/77655707
所谓无后效性原则,指的是这样一种性质:某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说,“未来与过去无关”,当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过程未来的演变。具体地说,如果一个问题被划分各个阶段之后,阶段k中的状态只能通过阶段k+1中的状态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没有关系,这就是无后效性
https://baike.baidu.com/item/%E6%97%A0%E5%90%8E%E6%95%88%E6%80%A7/1135283
3、什么是动态规划(Dynamic Programming)?动态规划的意义是什么?
https://www.zhihu.com/question/23995189

四、 完全背包
https://zhuanlan.zhihu.com/p/93857890
完全背包(unbounded knapsack problem)与01背包不同就是每种物品可以有无限多个:一共有N种物品,每种物品有无限多个,第i(i从1开始)种物品的重量为w[i],价值为v[i]。在总重量不超过背包承载上限W的情况下,能够装入背包的最大价值是多少?
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/139745.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2010-2017年WIND分省政府性债务余额面板数据

2010-2017年WIND分省政府性债务余额面板数据 1、时间&#xff1a;2010-2017年 2、指标&#xff1a;债务余额 3、范围&#xff1a;30个省 4、来源&#xff1a;wind 5、指标解释&#xff1a;地方政府债务分为一般债务和专项债务。 一般债务对应的是一般公共预算&#xff0c…

方案:浅析利用AI智能识别与视频监控技术打造智慧水产养殖监管系统

一、方案背景 针对目前水产养殖集约、高产、高效、生态、安全的发展需求&#xff0c;基于智能传感、智慧物联网、人工智能、视频监控等技术打造智慧水产系统&#xff0c;成为当前行业的发展趋势。传统的人工观察水产养殖方式较为单一&#xff0c;难以及时发现人员非法入侵、偷…

跨域问题解决方案(三种)

Same Origin Policy同源策略&#xff08;SOP&#xff09; 具有相同的Origin&#xff0c;也即是拥有相同的协议、主机地址以及端口。一旦这三项数据中有一项不同&#xff0c;那么该资源就将被认为是从不同的Origin得来的&#xff0c;进而不被允许访问。 Cross-origin resource…

SpringBean的生命周期

SpringBean的生命周期 SperingBean的生命周期是从Bean实例化之后&#xff0c;即通过反射创建出对象之后&#xff0c;到Bean成为一个完整对象&#xff0c;最终存储到单例池中&#xff0c;这个过程被称为Spring Bean的生命周期。Spring Bean的生命周期大体上分为三个阶段 Bean的…

Win7开启触摸键盘方法

在Win7系统中&#xff0c;自带有触摸屏幕键盘&#xff0c;能够在屏幕上显示虚拟键盘&#xff0c;让用户可以用指针设备或触屏等进行输入操作&#xff0c;那么Win7系统怎么开启触摸键盘呢&#xff1f;想知道的小伙伴可以跟着我一起来学习一下。 1、首先打开Win7系统的开始菜单&a…

小程序中如何查看会员的访问记录

​在小程序中&#xff0c;我们可以通过如下方式来查看会员的访问记录。下面是具体的操作流程&#xff1a; 1. 找到指定的会员卡。在管理员后台->会员管理处&#xff0c;找到需要查看访客记录的会员卡。也支持对会员卡按卡号、手机号和等级进行搜索。 2. 查看会员卡详情。点…

Smart UI Web 16.0.1 WebComponents htmlelements Crack

Javascript Web 组件库 Smart UI Web 组件库是您构建令人惊叹的 Web 应用程序所需的唯一套件。它包含 70 多个快速且专业设计的 UI 组件&#xff0c;可在单个包中实现美观且始终现代的 Web 应用程序。 具有高级功能的即用型Javascript 组件。只需几行代码即可使用数据网格、甘特…

解决编译中遇到的问题:Please port gnulib freadahead.c to your platform

今天在编译旧版的gzip-1.7时遇到了一个错误&#xff1a; error: #error "Please port gnulib freadahead.c to your platform! Look at the definition of fflush, fread, ungetc on your system, then report this to bug-gnulib." 在网上搜了一下解决方法&#xf…

400电话申请流程详解,助您快速办理联通、移动、电信400电话

导语&#xff1a;随着企业业务的发展&#xff0c;越来越多的企业开始关注400电话的申请与办理。本文将为您详细介绍联通、移动、电信400电话的申请流程&#xff0c;帮助您快速办理400电话&#xff0c;提升企业形象和客户服务质量。 一、联通400电话申请流程 咨询与选择&#x…

nginx知识点详解:反向代理+负载均衡+动静分离+高可用集群

一、nginx基本概念 1. nginx是什么&#xff0c;做什么事情&#xff1f; Nginx是一个高性能的HTTP和反向代理服务器&#xff0c;特点是占有内存少&#xff0c;并发能力强。Nginx转为性能优化而开发&#xff0c;能经受高负载考验。支持热部署&#xff0c;启动容易&#xff0c;运…

Avl树(有详细图解)

目录 介绍 引入 概念 特点 模拟实现 思路 插入 旋转 左旋 无子树 有子树 右旋 无子树 有子树 左右旋 引入(也就是有子树版本的抽象图解) 解决方法(也就是左右旋) 总结 无子树(也就是curright的位置就是newnode) 有子树 模型高度解释 旋转 更新三个…

资料分析笔记

统计术语 现期&#xff1a;现在的时间 基期&#xff1a;之前的时间 现期量 基期量 增长量&#xff08;有正负&#xff09; 增长率 【增幅、增速、r】&#xff08;有正负&#xff09; 同比&#xff1a;例&#xff1a;2014年5月 和 2013年5月 环比&#xff1a;例&#xff1a;20…

[Linux入门]---git命令行的基本使用

文章目录 1.git使用gitee仓库创建git使用测试ignore文件 1.git使用 git是一款对文件进行版本控制的软件&#xff0c;gitee、github是基于git软件搭建的网站&#xff0c;是可以对代码进行托管的平台&#xff1b;github是国外的网站&#xff0c;访问慢&#xff0c;不稳定&#xf…

基于微信小程序的高校宿舍信息管理系统设计与实现(源码+lw+部署文档+讲解等)

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…

【C++入门指南】C如何过渡到C++?祖师爷究竟对C++做了什么?

【C入门指南】C如何过渡到C&#xff1f;祖师爷究竟对C做了什么&#xff1f; 前言一、命名空间1.1 命名空间的定义1.2 命名空间使用 二、C输入、输出2.1 std命名空间的使用惯例 三、缺省参数3.1 缺省参数的定义3.2 缺省参数分类 四、函数重载4.1 函数重载概念4.2 C支持函数重载的…

逻辑漏洞挖掘之XSS漏洞原理分析及实战演练 | 京东物流技术团队

一、前言 2月份的1.2亿条用户地址信息泄露再次给各大公司敲响了警钟&#xff0c;数据安全的重要性愈加凸显&#xff0c;这也更加坚定了我们推行安全测试常态化的决心。随着测试组安全测试常态化的推进&#xff0c;有更多的同事对逻辑漏洞产生了兴趣&#xff0c;本系列文章旨在…

C++QT day11

绘制时钟 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPaintEvent>//绘制事件类 #include <QDebug>//信息调试类 #include <QPainter>//画家类 #include <QTimer>//定时器类 #include <QTime> #include &…

039_小驰私房菜_Camera perfermance debug

全网最具价值的Android Camera开发学习系列资料~ 作者:8年Android Camera开发,从Camera app一直做到Hal和驱动~ 欢迎订阅,相信能扩展你的知识面,提升个人能力~ 一、抓取trace 1. adb shell "echo vendor.debug.trace.perf=1 >> /system/build.prop" 2. …

zaabix实现对nginx监控

本文使用监控模板net.tcp.listen[port]实现监听端口 实验环境&#xff1a; 首先搭建好zabbix-server &#xff0c;zabbix-agenthttps://mp.csdn.net/mp_blog/creation/editor/132622769?spm1001.2014.3001.9457 而后在zabbix-agent主机上下载一个nginx 登录zabbix网站创建主…

你写过的最蠢的代码是?

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页: &#x1f405;&#x1f43e;猫头虎的博客&#x1f390;《面试题大全专栏》 &#x1f995; 文章图文并茂&#x1f996…