专题八：背包问题

devtools/2024/12/24 8:41:51/

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是记忆化搜索，并且掌握记忆化搜索算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：动态规划算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

背包问题 (Knapsack problem) 是⼀种组合优化的 NP完全问题。

问题可以描述为：给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如选
择，才能使得物品的总价格最⾼。

根据物品的个数，分为如下⼏类：

  • 01 背包问题：每个物品只有⼀个
  • 完全背包问题：每个物品有⽆限多个
  • 多重背包问题：每件物品最多有 si 个
  • 混合背包问题：每个物品会有上⾯三种情况......
  • 分组背包问题：物品有 n 组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品

其中上述分类⾥⾯，根据背包是否装满，⼜分为两类：

  • 不⼀定装满背包
  • 背包⼀定装满

优化⽅案：

  • 空间优化 - 滚动数组
  • 单调队列优化
  • 贪⼼优化

根据限定条件的个数，⼜分为两类：

  • 限定条件只有⼀个：⽐如体积 -> 普通的背包问题
  • 限定条件有两个：⽐如体积 + 重量 -> ⼆维费⽤背包问题

根据不同的问法，⼜分为很多类：

  • 输出⽅案
  • 求⽅案总数
  • 最优⽅案
  • ⽅案可⾏性

二、算法习题

2.1 第一题

题目链接：【模板】01背包_牛客题霸_牛客网

题目描述：

算法思路：

我们先解决第⼀问：

1. 状态表⽰：

 dp[i][j] 表⽰：从前 i 个物品中挑选，总体积「不超过」 j ，所有的选法中，能挑选出来的最⼤价值。 

2. 状态转移⽅程：

线性 dp 状态转移⽅程分析⽅式，⼀般都是根据「最后⼀步」的状况，来分情况讨论：

  1. 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j 。此时 dp[i][j] = dp[i - 1][j] ；
  2. 选择第 i 个物品：那么我就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[i]的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是这种状态不⼀定存在，因此需要特判⼀下。
  3. 综上，状态转移⽅程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] +w[i]) 。

3. 初始化：

我们多加⼀⾏，⽅便我们的初始化，此时仅需将第⼀⾏初始化为 0 即可。因为什么也不选，也能满⾜体积不⼩于 j 的情况，此时的价值为 0 。

4. 填表顺序：

根据「状态转移⽅程」，我们仅需「从上往下」填表即可。

5. 返回值：

根据「状态表⽰」，返回 dp[n][V] 。

接下来解决第⼆问：第⼆问仅需微调⼀下 dp 过程的五步即可。

因为有可能凑不⻬ j 体积的物品，因此我们把不合法的状态设置为 -1 。

1. 状态表⽰：

dp[i][j] 表⽰：从前 i 个物品中挑选，总体积「正好」等于 j ，所有的选法中，能挑选出来的最⼤价值。

2. 状态转移⽅程：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。但是在使⽤ dp[i - 1][j - v[i]] 的时候，不仅要判断 j >= v[i] ，⼜要判断 dp[i- 1][j - v[i]] 表⽰的情况是否存在，也就是 dp[i - 1][j - v[i]] != -1 。

3. 初始化：

 我们多加⼀⾏，⽅便我们的初始化：

  1. 第⼀个格⼦为 0 ，因为正好能凑⻬体积为 0 的背包；
  2. 但是第⼀⾏后⾯的格⼦都是 -1 ，因为没有物品，⽆法满⾜体积⼤于 0 的情况。  

4. 填表顺序：

根据「状态转移⽅程」，我们仅需「从上往下」填表即可。

5. 返回值：

由于最后可能凑不成体积为 V 的情况，因此返回之前需要「特判」⼀下。

代码呈现：

#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main() 
{
// 读⼊数据cin >> n >> V;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];
// 解决第⼀问for (int i = 1; i <= n; i++)for (int j = 0; 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;
// 解决第⼆问memset(dp, 0, sizeof dp);for (int j = 1; j <= V; j++) dp[0][j] = -1;for (int i = 1; i <= n; i++)for (int j = 0; 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;
}

2.2 第二题

题目链接：416. 分割等和子集 - 力扣（LeetCode）

题目描述：

算法思路：

如果数组能够被分成两个相同元素之和相同的⼦集，那么原数组必须有下⾯⼏个性质：

  1. 所有元素之和应该是⼀个偶数；
  2. 数组中最⼤的元素应该⼩于所有元素总和的⼀半；
  3. 挑选⼀些数，这些数的总和应该等于数组总和的⼀半。

根据前两个性质，我们可以提前判断数组能够被划分。根据最后⼀个性质，我们发现问题就转化成了「01 背包」的模型：

  1. 数组中的元素只能选择⼀次；
  2. 每个元素⾯临被选择或者不被选择的处境；
  3. 选出来的元素总和要等于所有元素总和的⼀半。
       

 1. 状态表⽰：

dp[i][j] 表⽰在前 i 个元素中选择，所有的选法中，能否凑成总和为 j 这个数。

2. 状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，分情况讨论：

  1. 不选择 nums[i] ：那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j] ；
  2. 选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是⼩于等于 j 。因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j - nums[i]] 。
  3. 综上所述，两种情况下只要有⼀种能够凑成总和为 j ，那么这个状态就是 true 。因此，状态转移⽅程为：dp[i][j] = dp[i - 1][j]if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j -nums[i]]

3. 初始化：

由于需要⽤到上⼀⾏的数据，因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰不选择任何元素，要凑成⽬标和 j 。只有当⽬标和为 0 的时候才能做到，因此第⼀⾏仅需初始化第⼀个元素 dp[0][0] = true

4. 填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5. 返回值：

根据「状态表⽰」，返回 dp[n][aim] 的值。其中 n 表⽰数组的⼤⼩， aim 表⽰要凑的⽬标和。

6. 空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。对于 01背包类型的，我们的优化策略是：

  1. 删掉第⼀维；
  2. 修改第⼆层循环的遍历顺序即可。

代码呈现：

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size(), sum = 0;for (auto x : nums)sum += x;if (sum % 2)return false;  // 如果不能平分，直接返回 falseint aim = sum / 2; // 定义⼀下⽬标值vector<vector<bool>> dp(n + 1, vector<bool>(aim + 1)); // 建表for (int i = 0; i <= n; i++)dp[i][0] = true;         // 初始化for (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];}
};

2.3 第三题

题目链接：494. 目标和 - 力扣（LeetCode）

题目描述：

  

算法思路：

本题可以直接⽤「暴搜」的⽅法解决。但是稍微⽤数学知识分析⼀下，就能转化成我们常⻅的「背
包模型」的问题。设我们最终选取的结果中，前⾯加 + 号的数字之和为 a ，前⾯加 - 号的数字之和为 b ，整个数组的总和为 sum ，于是我们有：

  • a + b = sum
  • a - b = target

上⾯两个式⼦消去 b 之后，可以得到 a = (sum + target) / 2也就是说，我们仅需在 nums 数组中选择⼀些数，将它们凑成和为 (sum + target) / 2 即可。问题就变成了 416. 分割等和⼦集 这道题。我们可以⽤相同的分析模式，来处理这道题。

1. 状态表⽰：

dp[i][j] 表⽰：在前 i 个数中选，总和正好等于 j ，⼀共有多少种选法。

2. 状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，我们有「选择」最后⼀个元素或者「不选择」最后⼀个元素两种策略：

  1. 不选 nums[i] ：那么我们凑成总和 j 的总⽅案，就要看在前 i - 1 个元素中选，凑成总和为 j 的⽅案数。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j] ；
  2. 选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是⼩于等于 j 。因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们能够凑成总和为j 的⽅案数，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j - nums[i]]
  3. 综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移⽅程为：dp[i][j] = dp[i - 1][j] if(nums[i - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i- 1]]

3. 初始化：

由于需要⽤到「上⼀⾏」的数据，因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰不选择任何元素，要凑成⽬标和 j 。只有当⽬标和为 0 的时候才能做到，因此第⼀⾏仅需初始化第⼀个元素 dp[0][0]= 1

4. 填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5. 返回值：

根据「状态表⽰」，返回 dp[n][aim] 的值。其中 n 表⽰数组的⼤⼩， aim 表⽰要凑的⽬标和。

6. 空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。对于 01背包类型的，我们的优化策略是：

  1. 删掉第⼀维；
  2. 修改第⼆层循环的遍历顺序即可 

代码呈现：

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size();int sum = 0;for (auto x : nums)sum += x;int aim = (sum + target) / 2;// 处理⼀下边界条件if (aim < 0 || (sum + target) % 2)return 0;vector<vector<int>> dp(n + 1, vector<int>(aim + 1)); // 建表dp[0][0] = 1;                                        // 初始化for (int i = 1; i <= n; i++)                         // 填表for (int j = 0; j <= aim; j++) {dp[i][j] = dp[i - 1][j];if (j >= nums[i - 1])dp[i][j] += dp[i - 1][j - nums[i - 1]];}// 返回结果return dp[n][aim];}
};

2.4 第四题

题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

题目描述：

  

算法思路：

1. 状态表⽰：

dp[i][j] 表⽰在前 i 个元素中选择，总和不超过 j，此时所有元素的「最⼤和」。

2. 状态转移⽅程：

 ⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，分情况讨论： 

  1. 不选 stones[i] ：那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j] ；
  2. 选择 stones[i] ：这种情况下是有前提条件的，此时的 stones[i] 应该是⼩于等于j 。因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - stones[i] 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j - stones[i]] + stones[i] 。
  3. 综上所述，我们要的是最⼤价值。因此，状态转移⽅程为：dp[i][j] = dp[i - 1][j]if(j >= stones[i]) dp[i][j] = dp[i][j] + dp[i - 1][j - stones[i]]+ stones[i] 。

3. 初始化：

由于需要⽤到上⼀⾏的数据，因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰「没有⽯⼦」。因此想凑成⽬标和 j ，最⼤和都是 0 。

4. 填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5. 返回值：

  1. 根据「状态表⽰」，先找到最接近 sum / 2 的最⼤和 dp[n][sum / 2] ；
  2. 因为我们要的是两堆⽯⼦的差，因此返回 sum - 2 * dp[n][sum / 2] 。

6. 空间优化：

所有的背包问题，都可以进⾏「空间」上的优化。对于 01背包类型的，我们的优化策略是：

  1. 删掉第⼀维；
  2. 修改第⼆层循环的「遍历顺序」即可。

代码呈现：

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 1. 准备⼯作int sum = 0;for (auto x : stones)sum += x;int n = stones.size(), m = sum / 2;// 2. dpvector<vector<int>> dp(n + 1, vector<int>(m + 1));for (int i = 1; i <= n; i++)for (int j = 0; j <= m; j++) {dp[i][j] = dp[i - 1][j];if (j >= stones[i - 1])dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);}// 3. 返回结果return sum - 2 * dp[n][m];}
};

三、结束语 

今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==​编辑​​  


http://www.ppmy.cn/devtools/144935.html

相关文章

公网IPV6如何使用IPV4网络访问——浪浪云

公网IPV6如何使用IPV4网络访问——浪浪云

此教程主要解决IPV6的网络无法被没有IPV6的网络环境所访问&#xff0c;所以可以通过浪浪云家的IPV6 CDN服务将公网IPV6服务转换为IPV4所访问&#xff0c;应用场景如下&#xff0c;例如家里有公网IPV6 或者服务器只有IPV6网络&#xff0c;都可以通过浪浪云CDN转换为IPV4访问 以浪…
阅读更多...
十二月第20讲：Python中指数概率分布函数的绘图详解

十二月第20讲：Python中指数概率分布函数的绘图详解

一、指数分布的理论概述 1. 定义与公式 指数分布是一种描述随机变量在一个固定底数上的对数值的分布情况&#xff0c;或者在概率理论和统计学中&#xff0c;用于描述泊松过程中事件之间的时间间隔的概率分布。具体来说&#xff0c;它表示事件以恒定平均速率连续且独立地发生的…
阅读更多...
汽车IVI中控开发入门及进阶（45）：凌阳科技车载娱乐芯片

汽车IVI中控开发入门及进阶（45）：凌阳科技车载娱乐芯片

概述： Sunplus科技有限公司成立于1990年，是一家领先的多媒体和汽车应用芯片提供商，如DVD播放器、便携式DVD播放器、家庭娱乐音频产品、汽车信息娱乐和高级驾驶辅助系统（ADAS）。与此同时，凌阳正在为消费类、便携式和连接设备上的广泛应用提供高速I/O IP、高性能数据转换I…
阅读更多...
探索AI安全治理，打造大模型时代的可信AI

探索AI安全治理，打造大模型时代的可信AI

探索AI安全治理&#xff0c;打造大模型时代的可信AI 0. 前言1. CCF-CV 企业交流会1.1 活动介绍1.2 走进合合信息 2. 大模型发展与安全挑战3. 打造大模型时代的可信 AI3.1 平衡生成式AI的创新与风险3.2 视觉内容安全技术的前沿进展与应用3.3 人工智能安全检测评估的逻辑和要点3.…
阅读更多...
【蓝桥杯每日一题】 蜗牛——动态规划

【蓝桥杯每日一题】 蜗牛——动态规划

蜗牛 蓝桥杯每日一题 2024-12-23 蜗牛 动态规划 题目描述 今天&#xff0c;一只蜗牛来到了二维坐标系的原点。 在 x 轴上有 n 根竹竿。它们平行于 y 轴&#xff0c;底部纵坐标为 0&#xff0c;横坐标分别为 x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1​,x2​,…,xn​。 竹…
阅读更多...
【hackmyvm】moosage靶机wp

【hackmyvm】moosage靶机wp

tags: HMV图片马文件上传perl脚本 这里写目录标题 2. 信息收集2.1. 端口扫描2.2. 目录扫描2.3. 源码获取 3. 图片马弹shell4. 提权baca用户5. 提权root5.1. 修改ssh登录脚本提权 靶机链接 https://hackmyvm.eu/machines/machine.php?vmMoosage 作者 sml 难度 ⭐️⭐️⭐️⭐…
阅读更多...
从用户视角出发：用例图分析家政预约小程序

从用户视角出发：用例图分析家政预约小程序

目录 1 引言&#xff1a;什么是用例图&#xff1f;它解决了什么问题&#xff1f;2 如何绘制用例图&#xff1f;2.1 绘制步骤 3 家政预约小程序用例图分析4 顾客用例详细分析4.1 注册/登录4.2 浏览服务4.3 搜索服务4.4 查看服务详情4.5 预订服务4.6 支付订单4.7 取消订单4.8 评价…
阅读更多...
CTF-WEB php-Session 文件利用 [第一届国城杯 n0ob_un4er 赛后学习笔记]

CTF-WEB php-Session 文件利用 [第一届国城杯 n0ob_un4er 赛后学习笔记]

step 1 搭建容器 教程 题目 github.com Dockerfile 有点问题,手动修复一下 FROM php:7.2-apacheCOPY ./flag /root COPY ./readflag / COPY ./html/ /var/www/html/ COPY ./php.ini /usr/local/etc/php/php.ini COPY ./readflag /readsecretRUN chmod 755 /var/www/html &…
阅读更多...
最新文章

Copyright @ 2022~2023