贪心算法之纪念品分组

vlambda
2020-04-13

贪心算法之纪念品分组

今天是周五，来道简单的吧，今天是贪心算法的最后一题了。

题目

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

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

解析

这道题

和P1090

十分相似

不过一个是

最小值

一个是最小相加次数

还有一定的上限

所以不同

下面是解析：

这道题

首先先排序

用最小的

和最大的比

一个一个往下比

找不到的话

就自算一堆

否则就把

那个数去掉

很简单

加油！

贪心算法之纪念品分组

代码

#include<bits/stdc++.h>

#include<iostream>

#include<cstdlib>

#include<cstdio>

using namespace std;

int n,a[30001],m,d,sum=0;

int main()

{

freopen("P1094_6.in","r",stdin);

freopen("P1094_6.out","w",stdout);

bool flag=true,flag2[30001];

memset(flag2,0,sizeof(flag2));

cin>>m;

cin>>n;

for(int i=1;i<=n;i++)

cin>>a[i];

sort(a+1,a+n+1);

for(int i=1;i<=n;i++)

{

flag=true;

for(int j=n;j>i;j--)

{

if(a[i]+a[j]<=m&&flag2[i]==0&&flag2[j]==0)

{

flag2[i]=1;

flag2[j]=1;

//cout<<a[i]<<" "<<a[j]<<endl;

flag=false;

d=j;

break;

}

if(flag==false)

{

for(int j=d;j<=n-1;j++)

a[j]=a[j+1];

n--;

}

//else cout<<a[i]<<endl;;

sum++;

}

cout<<sum<<endl;

return 0;

}

加油！

贪心算法之纪念品分组

预告：下期我打算写一下贪心算法的学习心得。

加油

往期精彩推荐

某些图片来自互联网，如有侵权，请联系删除

欢迎关注

亮星的信息学小屋

觉得有用，请点右下方“在看”，谢谢鼓励

vlambda博客
学习文章列表