【贪心算法】纪念品分组

简介: 【贪心算法】纪念品分组

回忆是捉不到的月光 握紧就变黑暗 让虚假的背影 消失于晴朗----陈奕迅

系列文章目录

第一篇 【贪心算法】初步介绍

第二篇  【贪心算法】删数问题

第三篇  【贪心算法】排队打水

第四篇  【贪心算法】最大整数

第五篇  【贪心算法】纪念品分组


一、题目

1、原题

1143. 【贪心算法】纪念品分组 (Standard IO)

时间限制: 1000 ms  空间限制: 262144 KB  具体限制  

题目描述

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。

你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。

输入

输入包含n+2行:

第1行包括一个整数w,为每组纪念品价格之和的上限。

第2行为一个整数n,表示购来的纪念品的总件数。

第3~n+2行每行包含一个正整数pi (5 <= pi <= w),表示所对应纪念品的价格。

输出

输出仅一行,包含一个整数,即最少的分组数目。

样例输入

100

9

90

20

20

30

50

60

70

80

90


样例输出

6

2、题意

输入一个有N个数字的数组,你要将它们分组(每组只能由两数组成),使各组两数之和(两数之和<=W)接近。输出满足上述条件的最小组数。

二、思路

1.读入数据

没什么难度,代码如下:

cin >>w>>n;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }

image.gif

2.核心内容

因为大小要最接近,因此用sort函数排序一下,然后左边(j),右边(i)所代表的物品相加后假若小于w就,可以将sum(表示最小组合数)++,还有记得把左端点j加1。

详细代码:

sort(p,p+n);
    int  j=0;
    int sum=0;
    for(int i = n-1; i>=j;i--)
  {
        if(p[i] + p[j] <= w)
    {
            sum++;
            j++;
        }
        else
    {
            sum++;
        }
    }

image.gif

3.输出

输出同样很简单,用“cout"展现出sum就行了。

代码……就不单独展示了!

三、AC代码

#include<iostream>
#include<algorithm>
using namespace std;
int p[100005];
int w, n;
int main (){
    cin >>w>>n;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    sort(p, p + n);
    int  j = 0;
    int sum =0;
    for(int i = n - 1; i >= j; i--){
        if(p[i] + p[j] <= w){
            sum++;
            j++;
        }
        else{
            sum++;
        }
    }
    cout << sum;
    return 0;
}

image.gif


总结

这就是此题详解,欢迎关注!

相关文章
|
5月前
|
算法 JavaScript
class074 背包dp-分组背包、完全背包【算法】
class074 背包dp-分组背包、完全背包【算法】
41 0
|
1天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。
|
22天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
本项目展示了一种结合粒子群优化(PSO)与分组卷积神经网络(GroupCNN)的时间序列预测算法。该算法通过PSO寻找最优网络结构和超参数,提高预测准确性与效率。软件基于MATLAB 2022a,提供完整代码及详细中文注释,并附带操作步骤视频。分组卷积有效降低了计算成本,而PSO则智能调整网络参数。此方法特别适用于金融市场预测和天气预报等场景。
|
4月前
|
存储 算法 安全
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
|
5月前
|
机器学习/深度学习 人工智能 运维
人工智能平台PAI 操作报错合集之请问Alink的算法中的序列异常检测组件,是对数据进行分组后分别在每个组中执行异常检测,而不是将数据看作时序数据进行异常检测吧
阿里云人工智能平台PAI (Platform for Artificial Intelligence) 是阿里云推出的一套全面、易用的机器学习和深度学习平台,旨在帮助企业、开发者和数据科学家快速构建、训练、部署和管理人工智能模型。在使用阿里云人工智能平台PAI进行操作时,可能会遇到各种类型的错误。以下列举了一些常见的报错情况及其可能的原因和解决方法。
|
5月前
|
JavaScript 算法 C语言
TypeScript算法专题 - blog5 - 单链表节点的`任意k个分组反转`的实现
TypeScript算法专题 - blog5 - 单链表节点的`任意k个分组反转`的实现
45 1
|
5月前
|
算法 安全 数据安全/隐私保护
C/C++学习 -- 分组加密算法(DES算法)
C/C++学习 -- 分组加密算法(DES算法)
141 0
|
5月前
|
算法 安全 数据安全/隐私保护
C/C++学习 -- 分组密算法(3DES算法)
C/C++学习 -- 分组密算法(3DES算法)
110 0
|
12月前
|
算法 安全 数据安全/隐私保护
C/C++学习 -- 分组加密算法(DES算法)
C/C++学习 -- 分组加密算法(DES算法)
280 0
|
12月前
|
算法 安全 数据安全/隐私保护
C/C++学习 -- 分组密算法(3DES算法)
C/C++学习 -- 分组密算法(3DES算法)
230 0