算法题（147）：纪念品分组

审题：
本题需要我们找出能使分组最少的纪念品分组组数

思路：
方法一：贪心

由于我们在放置礼物的时候需要让每一组的礼物价值都不超过w，且要尽可能的分更少组数，所以我们不会对价值最少的两件礼物分在一组，因为这样可能会导致分的组数变多。

eg：四个礼物，两个大礼物，两个小礼物。

我们把小的礼物放一起，大的礼物就只能分别单独放，此时分的组是三组

如果我们把一大一小的两个礼物放在一起，就可以只分两组

其实这也和我们放东西到行李箱一样，大的组合小的。

贪心策略：

先sort升序排序，用指针left和right分别指向最小的和最大的位置

若a[left]+a[right]<=w:将left与right位置的礼物分到一组，即left++，right--

若a[left]+a[right]>w:将right单独分一组（因为不可能再有礼物和他分一组了）,right--

贪心证明：

交换论证法：假设一个非贪心最优解，然后通过不改变“最优性”的调整，使得最优解调整为贪心解，那么贪心解即为最优解

1.对于a[left]+a[right]>w:最优解也是单独放a[right]，然后a[left]待定

2.对于a[left]+a[right]<=w:分三种情况

情况1：left单独放，right和另外一个礼物放

我们可以调整为right和left放一起,另外一个礼物单独放,因为left是最小的礼物，所以和另外一个礼物交换是合法的

情况2：right单独放，left和另外一个礼物放

这里也是同理

情况3：left和n放一起，right和m放一起

a[left]+a[n] <= w    a[right] + a[m] <= w

可以调整为a[left]+a[right] <= w 与 a[n]+a[m] <= w

因为a[n]<a[right]，而a[right] + a[m] <= w,所以a[n]+a[m]<=w是合法的

综上：所有情况都可以调整为贪心解法的解，贪心策略得证

解题：
 

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3e4 + 10;
int w, n;
int a[N];
int answer;
int main()
{//数据录入cin >> w >> n;for (int i = 1; i <= n; i++){cin >> a[i];}sort(a + 1, a + 1 + n);int left = 1;int right = n;while (left <= right){if (a[right] + a[left] <= w){left++;right--;}else{right--;}answer++;}cout << answer << endl;return 0;
}

P1094 [NOIP 2007 普及组] 纪念品分组 - 洛谷