2024/06/13--代码随想录算法3/17|01背包问题 二维、01背包问题 一维、416. 分割等和子集

本文主要是介绍2024/06/13--代码随想录算法3/17|01背包问题 二维、01背包问题 一维、416. 分割等和子集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
在这里插入图片描述

01背包问题 二维

卡码网链接
在这里插入图片描述

动态规划5步曲

  1. 确定dp数组(dp table)以及下标的含义:dp[i][j] :从下标为[0,i-1]个物品中任取,放进容量为j的背包,价值总和最大为多少。
  2. 确定递推公式,
    有两个方向可以推导出来dp[i][j] :
    不放物品i: dp[i][j] = dp[i - 1][j]
    放物品i: dp[i][j] = dp[i-1][j-weight[i]] + value[i]
    所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  3. dp数组如何初始化 【】
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步,如果把dp数组预先初始化为0了,这一步就可以省略,但很多同学应该没有想清楚这一点。dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}
  1. 确定遍历顺序【其实从递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了,那么 其他下标初始为什么数值都可以,因为都会被覆盖。】
  2. 举例推导dp数组
    先遍历物品,还是先遍历背包都可以,先遍历物品比较简单
def hanshu():M, bagweight = [int(x) for x in input().split()]weight = [int(x) for x in input().split()]value = [int(x) for x in input().split()]dp = [[0]*(bagweight+1) for i in range(M)]  #dp[i][j]代表从物品【0,i-1】让任意取,背包重量j,达到的最大价值#初始化for j in range(weight[0],bagweight+1):dp[0][j] = value[0]for i in range(1, M):for j in range(1, bagweight+1):if j>=weight[i]:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])else:dp[i][j] = dp[i-1][j]return dp[M-1][bagweight]maxs = hanshu()
print(maxs)

01背包问题 一维(滚动数组)

其实就是遍历物品i的时候,覆盖i-1的结果

动态规划5步曲

  1. 确定dp数组(dp table)以及下标的含义:dp[j] :容量为j的背包,价值总和最大为dp[i]。
  2. 确定递推公式,
    有两个方向可以推导出来dp[i][j] :
    不放物品i: dp[i][j] = dp[i - 1][j]
    放物品i: dp[i][j] = dp[i-1][j-weight[i]] + value[i]
    所以递归公式:此时dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值,
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  1. dp数组如何初始化
  2. 确定遍历顺序 倒序遍历背包是为了保证物品i只被放入一次!
    在这里插入图片描述
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]);}
}
def test_1_wei_bag_problem():weight = [1, 3, 4]value = [15, 20, 30]bagWeight = 4# 初始化dp = [0] * (bagWeight + 1)for i in range(len(weight)):  # 遍历物品for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagWeight])test_1_wei_bag_problem()

416. 分割等和子集

力扣链接
在这里插入图片描述
要明确本题中我们要使用的是01背包,因为元素我们只能用一次。

回归主题:首先,本题要求集合里能否出现总和为 sum / 2 的子集。
在这里插入图片描述

动态规划5步曲

  1. 确定dp数组(dp table)以及下标的含义:dp[j] :容量为j的背包,价值总和最大为dp[i]。
  2. 确定递推公式,
    有两个方向可以推导出来dp[i][j] :
    不放物品i: dp[i][j] = dp[i - 1][j]
    放物品i: dp[i][j] = dp[i-1][j-weight[i]] + value[i]
    所以递归公式:此时dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值,
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  1. dp数组如何初始化
  2. 确定遍历顺序 倒序遍历背包是为了保证物品i只被放入一次!
    == 如果 dp[j] = j 说明,集合中的子集总和正好可以凑成总和j,理解这一点很重要。==
    主要要理解,题目中物品是nums[i],重量是nums[i],价值也是nums[i],背包体积是sum/2。
    时间复杂度:O(n^2)
    空间复杂度:O(n)
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    # 集合中的元素正好可以凑成总和target
class Solution:def canPartition(self, nums: List[int]) -> bool:total_sum = sum(nums)if total_sum % 2 != 0:return Falsetarget_sum = total_sum // 2dp = [[False] * (target_sum + 1) for _ in range(len(nums) + 1)]# 初始化第一行(空子集可以得到和为0)for i in range(len(nums) + 1):dp[i][0] = Truefor i in range(1, len(nums) + 1):for j in range(1, target_sum + 1):if j < nums[i - 1]:# 当前数字大于目标和时,无法使用该数字dp[i][j] = dp[i - 1][j]else:# 当前数字小于等于目标和时,可以选择使用或不使用该数字dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]return dp[len(nums)][target_sum]

这篇关于2024/06/13--代码随想录算法3/17|01背包问题 二维、01背包问题 一维、416. 分割等和子集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例