贪心算法 - 学习笔记 【C++】

2024-12-09 - 第 38 篇
贪心算法 - 学习笔记
作者(Author): 郑龙浩 / 仟濹(CSND账号名)

贪心算法

学习课程：

https://www.bilibili.com/video/BV1f84y1i7mv/?spm_id_from=333.337.search-card.all.click&vd_source=2683707f584c21c57616cc6ce8454e2b

一、基本概念

贪心算法是一种在每个步骤都选择当前最优决策的算法。它只考虑当下的最好情况，希望通过这些局部最优选择来得到全局最优解。 特点是简单高效、具有无后效性。不过它不是万能的，有些情况不能通过它得到全局最优解，但在像哈夫曼编码这类有最优子结构的问题中很有效。

可以分为这四步( AI 生成 )

• 分解问题：将一个复杂的大问题分解为一系列的子问题。例如在活动安排问题中，把安排所有活动这个大问题，分解为一个个单独活动的选择。
• 确定贪心策略：找到一个合适的贪心策略，即确定在每个子问题中怎样选择才是局部最优。比如在找零问题中，贪心策略是优先使用面值大的硬币。
• 按照策略进行选择：依据确定好的贪心策略，在每个子问题里做出选择。以活动安排为例，就按照结束时间最早这个策略来选择活动。
• 合并结果：将所有子问题的局部最优解合并起来，得到最终的解。不过要注意这个解不一定是全局最优解。

简单一点讲就是：

• 无论能否吞得下，能吞一点。
• 根据当前的情况做出当前情况的最佳选择。
• 当做出选择的时候，要永不改变。反之，回溯算法可以“反悔”。
• 循环下去，使用“局部最优解”，逐步得到“整体最优解”

二、入门案例

海盗打劫商船，商船上装满古董，每件古董的重量不同，但每件古董的价值都相同，海盗船有最大载重的限制。

• 假设 最大载重 500

问，最多装几件古董，既不翻船又获利最大？

思路：

// 思路：
// 1. 先排序，从小到大 --> 目的就是从最轻的算起，逐步往重的方放，直到放到放不下为止
// 2. 从 0 开始，逐步累加，直到累加和大于 500 为止 --> 意思就是，边放边计算数量，直到船上放不开。
// 先累加，然后判断累加后的是否 >  最大载重// 若 > 最大载重，就退出循环// 若 < 最大载重，就继续累加

#include <iostream>
#include <algorithm>
using namespace std;
int main( void ){int data[] = { 8, 20, 5, 80, 3, 420, 14, 330, 70 };int max = 500, ans = 0, sum = 0; // 最大载重， 古董数量, 总重量int cnt = sizeof( data ) / sizeof( data[ 0 ] ); // 计算数组元素个数sort( data, data + cnt ); // 排序for ( int i = 0; i < cnt; i ++ ){// 先累加，然后判断累加后的是否 >  最大载重// 若 > 最大载重，就退出循环// 若 < 最大载重，就继续累加sum += data[ i ]; // 总重量累加if( sum > max ) // 如果当前重量大于最大载重，就退出循环break;ans ++; // 古董数量累加}cout << "古董数量：" << ans << endl;return 0;
}

三、初级案例 - 字节跳动笔试题

一个很长的花坛，一部分地已经种植了花，另一部分却没有。
花不能种植在相邻的地块上，否则它们会争夺水源，两者都会死去。

给你一个整数数组表示花坛，0 表示没种植花，1 表示种植了花。

给定一个数n，能不能种下 n 朵花？

分析 + 思路:

• 首先要知道：给定了一个数组(表示的花坛)，我们需要在给定的数组中种花。Eg: 10001 --> 可以种一朵花。 10010 --> 不可以种花. 10000001 / 1000001 --> 可以种两朵花
• 可以种花的条件是：当前位置的左边和右边都没有花。 Eg: 10001 --> 可以种一朵花。 10010 --> 不可以种花. 10000001 / 1000001 --> 可以种两朵花
• 最终计算的是，n朵花是否能全部种到 给定的花坛中去(数组)

1. 封装一个函数，用来判断 是否可以将 n 朵花 种完
   这个地方的判断需要特别注意，主要是 最两边的元素判断。
   特别容易出错。
2. 函数过程：遍历数组，如果当前位置可以种花，则 将当前位置的元素变为 “1”，并且 种植数量 ++
3. 判断 种植数量 是否等于 n ，如果等于 n ，则打印 Yes ，否则打印 No

// [字节跳动]笔试真题
// 一个很长的花坛，一部分地已经种植了花，另一部分却没有。
// 花不能种植在相邻的地块上，否则它们会争夺水源，两者都会死去。// 给你一个整数数组表示花坛，0 表示没种植花，1 表示种植了花。// **给定一个数n，能不能种下 n 朵花？**  能打印 Yes, 不能打印 No// 分析 + 思路：
// 首先要知道：给定了一个数组(表示的花坛)，我们需要在给定的数组中种花。
// 可以种花的条件是：当前位置的左边和右边都没有花。 Eg: 10001 --> 可以种一朵花。 10010 --> 不可以种花. 10000001 / 1000001 --> 可以种两朵花 
// 最终计算的是，n朵花是否能全部种到 给定的花坛中去(数组)// 1. 封装一个函数，用来判断 是否可以将 n 朵花 种完
// 这个地方的判断需要特别注意，主要是 最两边的元素判断。
// 特别容易出错。
// 2. 函数过程：遍历数组，如果当前位置可以种花，则 将当前位置的元素变为 “1”，并且 种植数量 ++ 
// 3. 判断 种植数量 是否等于 n ，如果等于 n ，则打印 Yes ，否则打印 No#include <iostream>
#include <vector>
// 判断是否可以将 n 朵花 种完
bool canPlant( bool *data, int dataSize, int n ){ //  data 表示数组首地址 dataSize 表示 存储的数据的宽度 即花坛的长度, n 表示需要种植的花的数量int count = 0; // 表示 种植数量for( int i = 0; i < dataSize;  i ++ ){if( data[ i ] == 0 && data[ i - 1 ] == 0 && data[ i + 1 ] == 0 && i - 1 >= 0 && i + 1 < dataSize ){ // 种植条件： 左右两边都没有花 && 边界条件：不能越界data[ i ] = 1; // 种花count ++; // 种植数量 ++}if( count >= n )    return 1; // 如果 count 种植数量 已经满足了 n 朵花，无需再进行多余的循环}return 0;
}
using namespace std;
int main( void ){bool data[] = { 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 };int n;cin >> n; // 输入种植几朵花if ( canPlant( data, sizeof(data) / sizeof(data[0]), n ) )cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}

四、中级案例 - 华为笔试题

给定一个整数数组，表示在同一行的行星。

每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向

正 表示向右移动， 负 表示向左移动.

每一颗行星 速度相同。

碰撞规则

1. 两个行星碰撞，较小的行星会爆炸。
2. 如果大小相同，则两颗都会爆炸。
3. 两颗移动方向相同的行星，永远不会发生碰撞。

分析 + 思路

分析 + 思路：

1. 封装一个函数，用来判断 + 计算 全部星球碰撞以后留下来的行星。并存入一个新的数组。

2. 函数过程：两个变量分别表示的 左边的行星 与 右边的行星

   几种情况：(1)为相同的情况；(2)(3)为不先相同的情况

   (1). 两个行星方向 【相同】，则永远不会发生碰撞

   (2). 两个行星方向 【相反】 && 左边质量 > 右边质量 --> 右边行星爆炸

   (3). 两个行星方向 【相反】 && 左边质量 < 右边质量 --> 左边行星爆炸

   (4). 两个行星方向 【相反】 && 左边质量 == 右边质量 --> 两个行星都爆炸

   注： 【情况(2)】 与 【情况(3)】【情况(4)】 合并为一种情况。

   循环 + 判断 完所有的情况以后，最后将留下来的行星 【存入】 新的数组中。

3. 将留下来的行星质量存入 传来的数组参数中。

可能会有错误。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 判断 + 计算 全部星球碰撞以后留下来的行星。并存入一个新的数组。
void newdata ( vector <int> &data, vector <int> &data2 ){// 使用 ector 就不用单独计算 数组的大小了// 参数： 原来容器， 容器大小， 新容器(存放星球爆炸以后的数据)int left = 0, right = 1; // 左边的星球 右边的星球;while( right < data.size()){ // 循环条件：右边的星球 【不超过】 星球容器宽度// 两个行星方向 【相同】，则永远不会发生碰撞if( data[left] * data[right] > 0 ){ // 方向一致，则永远不会发生碰撞【不爆炸】 【情况(1)】left = right;right ++;continue; // 没有爆炸，数据未更新，表示位置变量发生变化，重新进入循环// 注： 下面这种写法是有错误的，因为 left 并不一定 移动到 下一个星球 --> 可能会出现 bug// 只有 right 可以进行 ++// left++;// right++;} else if( data[left] * data[right] < 0 ){ // 两个行星方向 【相反】 --> 两种情况//【情况(2)】 --> 左边质量 > 右边质量 --> 右边行星爆炸if( abs(data[left]) > abs(data[right]) ){//【右边消失】data.at( right ) = 0; // 0 表示爆炸的星球left = right;right ++;continue; // 已经爆炸，数据更新，表示位置变量发生变化，重新进入循环} else if ( abs(data[left]) < abs(data[right]) )//【情况(3)】 左边质量 < 右边质量 --> 左边行星爆炸{ data.at( left ) = 0; // 0 表示爆炸的星球left = right;right ++;continue; // 已经爆炸，数据更新，表示位置变量发生变化，重新进入循环} else // 【情况(4)】左边质量 == 右边质量 --> 两个行星全都爆炸{data.at( left ) = 0; // 0 表示爆炸的星球data.at( right ) = 0; left = right;right ++;continue;}}// 判断 left 与 right 的指针位置已经爆炸if ( data[ left ] == 0 ) // 左边的星球已经爆炸{left = right;right ++;continue; // 没有爆炸，数据未更新，表示位置变量发生变化，重新进入循环}else if ( data[ right ] == 0 ){ // 右边的星球已经爆炸right ++; // 只需进行 右边位置移动即可continue;}// cout << right << endl;// cout << "123" << endl; // 测试死循环}// 将更新后的 为 "1" 的数据存入 新的容器中for( auto i = data.begin() ; i != data.end(); i++ ){if( *i!= 0 ){ // 将没爆炸的星球存入新的容器中data2.push_back( *i );}}
}
int main( void ){vector <int> data = {10, 2, -2, -2, -5}; // 随机写几个数据进行测试vector <int> data2; // 新的容器newdata ( data, data2 ); // 计算留下的星球cout << "爆炸个数:" << data.size() - data2.size() << endl; // 打印 爆炸的星球个数cout << "留下的星球：" << endl;for ( auto i = data2.begin(); i != data2.end(); i++ ){cout << *i << " "; // 打印 留下的星球}return 0;
}