[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

相关文章

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)