[Algorithm][动态规划][01背包问题][模板 背包][分割等和子集]详细讲解 +何为背包问题?

本文主要是介绍[Algorithm][动态规划][01背包问题][模板 背包][分割等和子集]详细讲解 +何为背包问题?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 0.何为背包问题?
  • 1.模板 背包
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 2.分割等和子集
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现


0.何为背包问题?

  • 背包问题:有限制条件下的"组合问题"

  • 你有一个背包,地上有一堆物品,挑选一些物品放入背包中

    • 问:最大能挑选出来的价值是多少?
  • 限制因素

    • 物品的属性:价值等
    • 背包的属性:容量大小等
    • 背包是要求必装满还是不必装满?
      请添加图片描述
  • 当研究一个问题,出现选或者不选的情况,思路就可以往01背包上靠

  • 注意:背包问题是必须要掌握的算法问题


1.模板 背包

1.题目链接

  • [模板] 背包

2.算法原理详解

  • 注意:01背包问题是所有背包问题的基础,此处的分析思路,可以用到很多题里面
  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • dp[i]:从前i个物品中选,所有选法中,能挑选出来的最大价值 ×
        • 无法得知背包容量
      • 不要求恰好装满
        • dp[i][j]:从前i个物品中挑选,总体积不超过j,所有选法中,能挑选出来的最大价值
      • 要求恰好装满
        • dp[i][j]:从前i个物品中挑选,总体积恰好等于j,所有选法中,能挑选出来的最大价值
    • 推导状态转移方程:根据最后一个位置的情况,分情况讨论

      • 不要求恰好装满:j - v[i] >= 0是为了确保背包此时容量足够塞下当前物品
        请添加图片描述

      • 要求恰好装满dp[i][j] == -1表示没有这种情况,即此时总体积凑不到j
        请添加图片描述

    • 初始化:

      • 不要求恰好装满vector<vector<int>> dp(n + 1, vector<int>(V + 1))
      • 要求恰好装满:第一行除第一个位置,其余都为-1
    • 确定填表顺序:从上往下

    • 确定返回值:

      • 不要求恰好装满dp[n][V]
      • 要求恰好装满dp[n][V] == -1 ? 0 : dp[n][V]
  • 滚动数组优化空间
    • 每次填值,只依赖上一行的值

      • 所以,理论上只需要两行一维数组,就可以解决问题
    • 可以一个一维数组就优化掉此问题

      • 但是如果从左往右遍历数组,会影响动态规划填值
        • 因为原本的填值过程,会依赖左上方的值
      • 此时,只需要从右往左遍历该数组,就不会影响动态规划的规程
        请添加图片描述

      请添加图片描述

    • 操作

      • 删除所有的横坐标
      • 修改一下j的遍历顺序
    • 注意不要去强行解释优化后的妆台表示以及状态转移方程,费时费力还没啥意义


3.代码实现

// v1.0
int main()
{int n = 0, V = 0;cin >> n >> V;vector<int> v(n + 1), w(n + 1);for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}vector<vector<int>> dp(n + 1, vector<int>(V + 1));// Q1for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i - 1][j];if(j >= v[i]){dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}}cout << dp[n][V] << endl;// Q2dp.resize(n + 1, vector<int>(V + 1));for(int i = 1; i <= V; i++){dp[0][i] = -1;}for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i - 1][j];if(j >= v[i] && dp[i - 1][j - v[i]] != -1){dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}
-----------------------------------------------------------------------------
// v2.0 滚动数组优化
int main()
{int n = 0, V = 0;cin >> n >> V;vector<int> v(n + 1), w(n + 1);for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}vector<int> dp(V + 1);// Q1for(int i = 1; i <= n; i++){for(int j = V; j >= v[i]; j--){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[V] << endl;// Q2dp.resize(V + 1, 0);for(int i = 1; i <= V; i++){dp[i] = -1;}for(int i = 1; i <= n; i++){for(int j = V; j >= v[i]; j--){if(dp[j - v[i]] != -1){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}}cout << (dp[V] == -1 ? 0 : dp[V]) << endl;return 0;
}

2.分割等和子集

1.题目链接

  • 分割等和子集

2.算法原理详解

  • 问题转化:在数组中选择一些数出来,让这些数的和等于sum / 2 --> 01背包
  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • dp[i]j]:从前i个数中****,所有的选法中,能否凑成j这个数
    • 推导状态转移方程:根据最后一个位置的情况,分情况讨论

      • dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
        请添加图片描述
    • 初始化:

      • 多开一行及一列虚拟结点
        请添加图片描述
    • 确定填表顺序:从上往下

    • 确定返回值:dp[n][sum / 2]

  • 滚动数字优化同[模板] 背包

3.代码实现

// v1.0
bool canPartition(vector<int>& nums) 
{int n = nums.size(), sum = 0;for(auto& x : nums){sum += x;}if(sum % 2) return false;int aim = sum / 2;vector<vector<bool>> dp(n + 1, vector<bool>(aim + 1));// Initfor(int i = 1; i <= n; i++){dp[i][0] = true;}// DPfor(int i = 1; i <= n; i++){for(int j = 1; j <= aim; j++){dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1]){dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];}}}return dp[n][aim];
}
----------------------------------------------------------------------
// v2.0 滚动数组优化
bool canPartition(vector<int>& nums) 
{int n = nums.size(), sum = 0;for(auto& x : nums){sum += x;}if(sum % 2) return false;int aim = sum / 2;vector<bool> dp(aim + 1);                dp[0] = true;// DPfor(int i = 1; i <= n; i++){for(int j = aim; j >= nums[i - 1]; j--){dp[j] = dp[j] || dp[j - nums[i - 1]];}}return dp[aim];
}

这篇关于[Algorithm][动态规划][01背包问题][模板 背包][分割等和子集]详细讲解 +何为背包问题?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

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

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu