当前位置：首页 > 编程日记 > 正文

贪心：assign cookies分糖果

编程日记 2024-04-21 14:30:00

贪心算法的核心：
遵循某种规律，使用最少的资源来完成目标

所以在了解贪心算法的时候需要明确两点

寻找共有的规律
每一步的迭代使用最优的策略（消耗最少的资源）

问题如下：
已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s >= 某个孩子的需求因子g时，代表该糖果可以满足该孩子;求使用这些糖果，最多能满足多少孩子?(注意，某个孩子最多只能用1个糖果满足)
类似：g = [2, 5, 9, 9, 10, 15] ，糖果大小：s = [1, 3, 6, 8, 20]

根据贪心算法的核心分析：

规律
假如糖果大小不满足一个孩子的需求因子，则比该需求因子更小的都不会被满足
使用最小的糖果能够满足孩子，则可以留下较大的糖果满足更高需求因子的孩子
迭代策略
使用较小的糖果满足来满足较小需求因子的孩子

实现如下（文末有完整测试代码）：

/*
需要注意：一个糖果满足了一个孩子之后就不能满足其他的孩子了
*/
int allocate_num(vector<int> &child, vector<int> &candy) {if(child.size() == 0 || candy.size() == 0) {return 0;}/*根据规律，调整糖果大小和需求因子的序列*/sort(child.begin(),child.end()); sort(candy.begin(),candy.end());int child_num = 0;int candy_num = 0;/*迭代策略：只有糖果大小 >= 孩子的需求因子之后才能算满足*/while(child_num < child.size() && candy_num < candy.size()) {if(candy[candy_num] >= child[child_num]) {child_num ++;}candy_num ++;}/*返回可以分配给孩子的数量*/return child_num;
}

测试代码如下:

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;int allocate_num(vector<int> &child, vector<int> &candy) {if(child.size() == 0 || candy.size() == 0) {return 0;}sort(child.begin(),child.end());sort(candy.begin(),candy.end());int child_num = 0;int candy_num = 0;while(child_num < child.size() && candy_num < candy.size()) {if(candy[candy_num] >= child[child_num]) {child_num ++;}candy_num ++;}return child_num;
}int main() {vector<int> child;vector<int> candy;int tmp_child;int tmp_candy;cout << "input child " << endl;for (int i = 0;i < 5; ++i) {cin >> tmp_child;child.push_back(tmp_child);}cout << "input candy " << endl;for (int i = 0;i < 5; ++i) {cin >> tmp_candy;candy.push_back(tmp_candy);}cout << "the num of child can be allocate is " << allocate_num(child,candy) << endl;return 0;
}

输入输出如下:

input child 
2 5 9 9 10
input candy 
1 3 6 8 20
the num of child can be allocate is 3

https://www.dkcj.cn/info/5015.html

mimo系统matlab,OFDM—MIMO系统的matlab程序

【实例简介】MIMO OFDM Simulator:OFDM.m: OFDM Simulator (outer function)create_channel.m: Generates a Rayleigh fading frequency-selective channel, parametrized by the antenna configuration, the OFDM configuration, and the power-delay profile.svd_decompose_c…

编程日记2024/04/21 14:00:00

贪心：assign cookies分糖果

相关文章：

mimo系统matlab,OFDM—MIMO系统的matlab程序

软件行业项目经理主要的职责是什么?（转）

android interview 1

Spring Boot 的 10 个核心模块

贪心：Wiggle Subsequence 摇摆序列

php 腾讯云实时音视频,腾讯云视频 -实时音视频学习日志

juery mobile select下来菜单选项提交form问题

android GridView item中组件获取焦点

Login failed for user 'NT AUTHORITY\SYSTEM'. 原因: 无法打开明确指定的数据库。异常处理...

n-netstat 查看网络状态命令

php win memcached 5.4,CentOS 5.4下Memcache的安装步骤(Linux+Nginx+PHP+Memcached) 电脑维修技术网...

LomoX 桌面UI框架更新，增加资源管理

Python 数据类型：列表

贪心：remove K digits移除K个数字

oracle 分组排序 update,oracle分组排序

QLocalServer与QLocalSocket进程通讯

JDBC编程步骤

（13）中值滤波和双边滤波

贪心：Jump Game 跳跃游戏

MFC之按键消息（长按处理）

服务器oracle11g卸载,卸载Oracle11g步骤详解

Fedora下配置网卡

echarts相关设置

贪心：jump 游戏（获取最少跳跃的次数以及跳跃路径）

ADO.NET事务

oracle表中怎么去重复,oracle去掉表重复数据

JavaIO操作(1)字节流和字符流-1

7min到40s：SpringBoot 启动优化实践

SpringBoot系列教程之Bean之指定初始化顺序的若干姿势

在Java中使用WebSocket