代码随想录算法训练营第43天(py)| 动态规划 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、爬楼梯

本文主要是介绍代码随想录算法训练营第43天(py)| 动态规划 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、爬楼梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

完全背包

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。
01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。

for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

而完全背包的物品是可以添加多次的,所以要从小到大去遍历,即:

// 先遍历物品,再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

在01背包中,遍历物品在外层,遍历容量在内层;
而在完全背包中,两个for遍历的先后顺序不影响.

卡码网-52.携带研究材料

卡码链接

题目

小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的重量,并且具有不同的价值。

小明的行李箱所能承担的总重量为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料可以选择无数次,并且可以重复选择。

输入描述

第一行包含两个整数,N,V,分别表示研究材料的种类和行李空间
接下来包含 N 行,每行两个整数 wi 和 vi,代表第 i 种研究材料的重量和价值

输出描述

输出一个整数,表示最大价值。

if __name__ == '__main__':# 行李容量空间N, bagWeight = map(int, input().split())# 初始化重量和价值的数组weight = []value = []# 逐行读取接下来的N行数据for _ in range(N):w, v = map(int, input().split())weight.append(w)# 重量value.append(v) # 价值dp = [0] * (bagWeight + 1)for i in range(len(weight)):  # 遍历物品for j in range(weight[i] , bagWeight+1):  # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[-1])

518. 零钱兑换 II

力扣链接
给定不同面额的硬币coins和一个总金额amount。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

  1. 确定dp含义
    凑成总金额j的货币组合数为dp[j]
  2. 确定递推公式
    dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加。
    所以递推公式:dp[j] += dp[j - coins[i]];
  3. 初始化
    dp[0] = 1
  4. 确定遍历方向
    外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)。计算的是组合数
    内层for循环遍历物品(钱币),外层for遍历背包(金钱总额)。计算的是排列数
class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0]*(amount + 1)dp[0]=1for i in range(len(coins)):for j in range(coins[i], amount+1):dp[j]+=dp[j - coins[i]]return dp[-1]

377. 组合总和 Ⅳ

力扣链接
给定一个由正整数组成且不存在重复数字的数组nums,找出和为给定目标正整数target的排列的个数。

  1. 确定dp含义
    凑成目标正整数为i的排列个数为dp[i]
  2. 确定递推公式
    dp[i] += dp[i - nums[j]]
  3. 初始化
    dp[0] = 1
  4. 确定遍历方向
    求排列数就是外层for遍历背包,内层for循环遍历物品
    target(背包)放在外循环,将nums(物品)放在内循环,内循环从前到后遍历。
class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0]*(target+1)dp[0]=1for i in range(1, target+1):for j in range(len(nums)):if i - nums[j] >= 0:dp[i] += dp[i - nums[j]]return dp[-1]

70. 爬楼梯

卡码链接

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

输入描述

输入共一行,包含两个正整数,分别表示n, m

输出描述

输出一个整数,表示爬到楼顶的方法数。

思路

完全背包问题,1阶,2阶,… m阶就是物品,楼顶就是背包。

  1. 确定dp含义
    dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法。
  2. 确定递推公式
    求装满背包有几种方法,递推公式一般都是dp[i] += dp[i - nums[j]];
    本题,dp[i]有几种来源,dp[i - 1],dp[i - 2],dp[i - 3] 等等,即:dp[i - j]
    那么递推公式为:dp[i] += dp[i - j]
  3. 初始化
    dp[0]=1
  4. 确定遍历方向
    target放在外循环,将nums放在内循环
if __name__ == '__main__':n, m = map(int, input().split())dp = [0] * (n+1)dp[0] = 1for j in range(1, n+1):for i in range(1, m+1):if j >= i:dp[j] += dp[j-i]print(dp[-1])

这篇关于代码随想录算法训练营第43天(py)| 动态规划 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、爬楼梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075707

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

一文教你Python引入其他文件夹下的.py文件

《一文教你Python引入其他文件夹下的.py文件》这篇文章主要为大家详细介绍了如何在Python中引入其他文件夹里的.py文件,并探讨几种常见的实现方式,有需要的小伙伴可以根据需求进行选择... 目录1. 使用sys.path动态添加路径2. 使用相对导入(适用于包结构)3. 使用pythonPATH环境

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时