代码随想录算法训练营DAY10之动态规划（二）背包问题

news/2024/10/5 14:31:47/

01背包理论基础

406、分割等和子集

力扣题目链接

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

  • 输入: [1, 5, 11, 5]
  • 输出: true

思路分析（动规五步曲）：

1.确定dp数组以及下标的含义

01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。

本题中每一个元素的数值既是重量，也是价值。

套到本题，dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。

那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。

2.确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3.初始化dp数组

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

4.确定遍历顺序

如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历

我觉得这是最难想明白的，最重要的是想通滚动数组只有一层，所以要从后往前遍历，不然就多算了，就成完全背包了

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}
}

5.举例推导dp数组

code（1）:

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;// dp[i]中的i表示背包内总和// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了vector<int> dp(10001, 0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 也可以使用库函数一步求和// int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 == 1) return false;int target = sum / 2;// 开始 01背包for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] == target) return true;return false;}
};

code（2）：

其实，只要给数组排序，然后从小到大遍历，只要和为target就返回true

class Solution {
public:bool canPartition(vector<int>& nums) {sort(nums.begin(),nums.end());int sum=0;for(int num:nums)sum+=num;if(sum%2==1)return false;int target=sum/2;int cur=0;for(int num:nums){cur+=num;if(cur==target)return true;}return false;}
};

1049、最后一块石头的重量||

力扣题目链接

题目描述

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

  • 输入：[2,7,4,1,8,1]
  • 输出：1

思路分析

只要想明白，其实是要把石堆尽可能的分为相近的两堆，也就是sum/2,分析到这里，就能发现跟上一题很相似了，只是最后的处理有一点点不同，return sum-dp[target]-dp[target]

code：

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//尽可能分为两份等可能的vector<int>dp(15001,0);int sum=0;for(int i:stones){sum+=i;}int target=sum/2;//dp物品和背包for(int i=0;i<stones.size();i++){for(int j=target;j>=stones[i];j--){dp[j]=max(dp[j],(dp[j-stones[i]]+stones[i]));}}return sum-dp[target]-dp[target];}
};

494、目标和

力扣题目链接

题目描述：

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。

思路分析（五步曲）：

救命，太强啦！！！怎么想到的啊

这道题目咋眼一看和动态规划背包啥的也没啥关系。

本题要如何使表达式结果为target，

既然为target，那么就一定有 left组合 - right组合 = target。

left + right = sum，而sum是固定的。right = sum - left

left - (sum - left) = target 推导出 left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

注意：

这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了。

code1：

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};

code2：

二维dp：以下写明五步曲的部分步骤：

1.确定dp数组以及下标的含义

现在算是体会到这个的重要性了

先用 二维 dp数组求解本题，dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

2.确定递推公式

二维廷简单的，跟之前讲的二维dp公式一致

  • 不放物品i：即背包容量为j，里面不放物品i，装满有dp[i - 1][j]中方法。

  • 放物品i： 即：先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[i - 1][j - 物品i容量] 种方法。

本题中，物品i的容量是nums[i]，价值也是nums[i]。

递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

此时应该注意到，j - nums[i] 作为数组下标，如果 j - nums[i] 小于零呢？

说明背包容量装不下 物品i，所以此时装满背包的方法值 等于 不放物品i的装满背包的方法，即：dp[i][j] = dp[i - 1][j];

所以递推公式：

if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

3.dp数组的初始化

只有背包容量为 物品0 的容量的时候，方法为1，正好装满。

其他情况下，要不是装不满，要不是装不下。

所以初始化：dp[0][nums[0]] = 1 ，其他均为0 。

 左边一列就是 2^t种，初始化为：

int numZero = 0;
for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(2.0, numZero);
}

全部代码如下： 

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));// 初始化最上行if (nums[0] <= bagSize) dp[0][nums[0]] = 1; // 初始化最左列，最左列其他数值在递推公式中就完成了赋值dp[0][0] = 1; int numZero = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(2.0, numZero);}// 以下遍历顺序行列可以颠倒for (int i = 1; i < nums.size(); i++) { // 行，遍历物品for (int j = 0; j <= bagSize; j++) { // 列，遍历背包if (nums[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];}}return dp[nums.size() - 1][bagSize];}
};

474、一和零

力扣题目链接

题目描述：

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

  • 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

  • 输出：4

  • 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

思路分析：

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

1.确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

五步曲：

2.确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

3.初始化

如上

4.遍历顺序

如上

5.举例推导dp数组√

code：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};


http://www.ppmy.cn/news/1534160.html

相关文章

UniVue大版本更新：UniVue2.0.0-preview

UniVue大版本更新：UniVue2.0.0-preview

大版本发布说明 距离上次更新好像已经过去很久了&#xff0c;最近太忙了没时间维护新版本&#xff0c;也是自己在使用的过程中发现了很多问题也有了更多的灵感&#xff0c;由于和之前的版本区别太大&#xff0c;决定重新开一个大版本。这个UniVue2之后的版本追求是性能&#xf…
阅读更多...
鸿蒙 HarmonyNext 与 Flutter 的异同之处

鸿蒙 HarmonyNext 与 Flutter 的异同之处

HarmonyNext 是华为推出的面向未来的应用开发框架&#xff0c;依托于鸿蒙&#xff08;HarmonyOS&#xff09;生态系统&#xff0c;特别适用于多设备协同、物联网&#xff08;IoT&#xff09;等场景。Flutter 是 Google 开发的跨平台 UI 框架&#xff0c;旨在通过单套代码运行在…
阅读更多...
React -AppVarContext.Provider 提供者组件

React -AppVarContext.Provider 提供者组件

AppVarContext.Provider 是一个 React 上下文提供者&#xff0c;通常用于在组件树中提供共享的状态或数据。下面将详细解释 AppVarContext.Provider 的作用和如何使用它。展示如何使用 AppVarContext.Provider 来管理全局状态 1. 什么是上下文&#xff08;Context&#xff09;…
阅读更多...
leetcode_55:跳跃游戏

leetcode_55:跳跃游戏

给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输…
阅读更多...
联想电脑怎么开启vt_联想电脑开启vt虚拟化教程(附intel和amd主板开启方法)

联想电脑怎么开启vt_联想电脑开启vt虚拟化教程(附intel和amd主板开启方法)

最近使用联想电脑的小伙伴们问我&#xff0c;联想电脑怎么开启vt虚拟。大多数可以在Bios中开启vt虚拟化技术&#xff0c;当CPU支持VT-x虚拟化技术&#xff0c;有些电脑会自动开启VT-x虚拟化技术功能。而大部分的电脑则需要在Bios Setup界面中&#xff0c;手动进行设置&#xff…
阅读更多...
确保从IP池提取的IP是可用的对于数据抓取或其他网络活动至关重要。以下是一些确保IP可用性的有效方法：

确保从IP池提取的IP是可用的对于数据抓取或其他网络活动至关重要。以下是一些确保IP可用性的有效方法：

1. IP验证 Ping测试&#xff1a;使用Ping命令来检查IP地址的响应情况。可用的IP地址应该能够成功响应Ping请求。 端口扫描&#xff1a;使用工具&#xff08;如Nmap&#xff09;扫描IP地址上的特定端口&#xff0c;以确认目标服务是否正常运行。例如&#xff0c;HTTP端口&#…
阅读更多...
vuepress 浏览器加载缓存，总是显示旧页面，无法自动刷新数据的解决方法

vuepress 浏览器加载缓存，总是显示旧页面，无法自动刷新数据的解决方法

vuepress 采用多页面形式&#xff0c;每个md文件在打包时&#xff0c;都会被转为一个html页面&#xff1b;而浏览器默认会缓存页面&#xff0c;导致更新的页面必须手动刷新才行 对于更新较为频繁的文档 全局可在config.js里设置 参考文档: https://vuepress.github.io/zh/ref…
阅读更多...
如何使用ssm实现基于web的网站的设计与实现+vue

如何使用ssm实现基于web的网站的设计与实现+vue

TOC ssm756基于web的网站的设计与实现vue 绪论 1.1 研究背景 当前社会各行业领域竞争压力非常大&#xff0c;随着当前时代的信息化&#xff0c;科学化发展&#xff0c;让社会各行业领域都争相使用新的信息技术&#xff0c;对行业内的各种相关数据进行科学化&#xff0c;规范…
阅读更多...
最新文章

Copyright @ 2022~2023