当前位置: 首页 > news >正文

做网站的资料修改搜索引擎调词平台多少钱

做网站的资料修改,搜索引擎调词平台多少钱,上海十大it外包公司,寻找聊城做网站的公司背包问题其实有很多种,01背包是最基础也是最经典的,软工计科学生一定要掌握的。 01背包问题 代码随想录 视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经…

背包问题其实有很多种,01背包是最基础也是最经典的,软工计科学生一定要掌握的。


01背包问题

代码随想录

视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

思路

        直接上动态规划五部曲

1、dp数组及其下标的含义

对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

2.确定递推公式

再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

那么可以有两个方向推出来dp[i][j],

  • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)
  • 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.初始化

首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。

再看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号0的物品重量还小。

当j >= weight[0]时,dp[0][j] 应该是value[0],因为背包容量放足够放编号0物品。

4.确定遍历顺序

在如下图中,可以看出,有两个遍历的维度:物品与背包重量

动态规划-背包问题3

那么问题来了,先遍历 物品还是先遍历背包重量呢?

其实都可以!! 但是先遍历物品更好理解

5.举例验证,直接看链接里的吧。

代码
def test_2_wei_bag_problem1():weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4# 二维数组dp = [[0] * (bagweight + 1) for _ in range(len(weight))]# 初始化for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]# weight数组的大小就是物品个数for i in range(1, len(weight)):  # 遍历物品for j in range(bagweight + 1):  # 遍历背包容量if j < weight[i]:dp[i][j] = dp[i - 1][j]else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])print(dp[len(weight) - 1][bagweight])test_2_wei_bag_problem1()

01背包滚动数组

代码随想录

视频讲解:带你学透01背包问题(滚动数组篇) | 从此对背包问题不再迷茫!_哔哩哔哩_bilibili

 看链接吧,老是复制粘贴累了。


416.分割等和子集

本题是 01背包的应用类题目

代码随想录

视频讲解:动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集_哔哩哔哩_bilibili

思路

        就是01背包的应用,背包的大小是总和的一半,遍历每一个物品,看看遍历到最后能不能装满这个背包。

代码(二维版本在链接里)
class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums) % 2 != 0:return Falsetarget = sum(nums) // 2dp = [0] * (target + 1)for num in nums:for j in range(target, num-1, -1):dp[j] = max(dp[j], dp[j-num] + num)return dp[-1] == target
http://www.khdw.cn/news/21934.html

相关文章:

  • 关于网页设计的网站世界足球世界排名
  • 专业网站制作公司名称国际最新消息
  • javaweb做网站的流程百度网页版怎么切换
  • 青羊区电商型网站建设设计5g网络优化工程师
  • 凡客网站做SEO能被收录吗汕头百度seo公司
  • 一流的盘锦网站建设网站seo属于什么专业
  • wordpress+HTML5游戏宁波网络推广优化公司
  • 仿360电影网站源码永久免费国外域名注册
  • 全面的手机网站建设郑州网络营销公司有哪些
  • 网络系统工程设计是干什么的什么是sem和seo
  • 软件技术服务包括哪些内容优化建站
  • 服务网站建设推广网站建立具体步骤是
  • 宣武富阳网站建设互联网怎么打广告推广
  • 做自媒体都有什么网站seo优化软件
  • 哪个网站做服装批发比较好培训机构网站模板
  • 未来网站建设想法2023年8月份新冠
  • 网站后台难做吗在线建站模板
  • 网站内地图位置怎么做杭州网站seo推广软件
  • 简单大气网站欣赏万网域名交易
  • 广州微信网站设计制作重庆网站seo搜索引擎优化
  • 网站项目策划书内容模板百度文库官网登录入口
  • 班级网站设计报告 dreamwaverseo网站推广助理
  • 做网站编程在程序北京网站外包
  • 哈尔滨微网站建设营销软文写作
  • 莱芜招聘的网站优秀网站seo报价
  • 网站开发 模块营销战略
  • 品牌企业网站建设公司价格营销广告文案
  • 那个网站专门做二手衣服西安seo霸屏
  • 网站收录提交入口网址h5下一页
  • 网站制作模版搜索最多的关键词的排名