贪心算法4：纪念品分组

红太狼 2022-05-06 12:58 179阅读 0赞

> 几个贪心的例子：

1. 最优装载问题：

给n个物体，第i个物体重量为wi，选择尽量多的物体，使得总重量不超过C。

贪心策略：将物体的重量从小到大排序，每次选择最轻的物体。

[https://blog.csdn.net/yanyanwenmeng/article/details/83005293][https_blog.csdn.net_yanyanwenmeng_article_details_83005293]

2. 部分背包问题：

有n个物体，第i个物体的重量为wi,价值为Vi,在总重量不超过C的情况下让总价值尽量高。

贪心策略：前提是物体可以分隔，每次选择单位重量价值最大的物体。

[https://blog.csdn.net/yanyanwenmeng/article/details/83008780][https_blog.csdn.net_yanyanwenmeng_article_details_83008780]

3. 乘船问题：有n个人，第i个人的重量为wi，每艘船的载重量为C，最多乘两个人，用最少的船装载所有人。

贪心策略：最轻的人和尽量重的人配对。

关于装东西的问题，贪心策略都是要使得剩余的空间尽量小，所利用的空间尽量大。所以也可以选择从最重的人开始配对。

例如：有6个人，每个人的重量分别是：6 4 8 3 5 9，每艘船的重量不超过9，最多乘两个人，用最少的船装载所有人。

（1）排序：3 4 5 6 8 9

（2）9 8 6+3 5+4 一共需要4艘船。每次从最重的开始装，如果没超过载重，从最轻的开始配对，配对完成就从待选序列中删掉。

## 题目描述 ##

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

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

输入

输入数据有多组，每组数据包含n+2行：  
第1行包括一个整数w，为每组纪念品价格之和的上限。  
第2行为一个整数n，表示购来的纪念品的总件数。  
第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。(1<= n <= 30000, 80 <= w <= 200)

输出

每组数据输出一行，包含一个整数，即最少的分组数目。

样例输入

100  
9  
90  
20  
20  
30  
50  
60  
70  
80  
90

样例输出

> 【思路】典型的乘船问题，先选择价格最大的，然后和价格最小的配对，看是否满足条件。
> 
> 【注意】循环条件可以采用两个指针逼近的方法。

#include<iostream>
    #include<algorithm>
    #define MAXN 30005
    using namespace std;
    int a[MAXN];
    int main()
    {
    	int w,n;
    	cin >> w >> n;
    	for(int i = 1; i <= n; ++i)
    		cin >> a[i];
    	sort(a+1,a+1+n);
    	int l, r;//左指针、右指针 
    	l = 1;
    	r = n;
    	int sum = 0;
    	while(l <= r)
    	{
    		if(a[l] + a[r] <= w)
    		{
    		//	cout << "a[" << l << "]= " << a[l] << " " << "a[" << r << "]= " << a[r] << endl;
    			++l;
    			--r;
    			++sum; 
    		//	cout << "sum = " << sum << endl;
    		}
    		else
    		{
    			//cout << "a[" << r << "]= " << a[r] << endl; 
    			--r;
    			++sum;
    			//cout << "sum = " << sum << endl;
    		}	
    	}
    	cout << sum << endl;
    	return 0; 
    }

[https_blog.csdn.net_yanyanwenmeng_article_details_83005293]: https://blog.csdn.net/yanyanwenmeng/article/details/83005293
[https_blog.csdn.net_yanyanwenmeng_article_details_83008780]: https://blog.csdn.net/yanyanwenmeng/article/details/83008780