贪心算法专题：最大子段和与纪念品分组

2.1.4 贪心策略证明

（1）证明方法：反证法 （2）证明思路：抓住向后加的时候，只要不小于 0，就会一直加下的主线去在累加的过程中算出一段区间和 sum[a,b] < 0，如果不舍弃这一段，那么 [a, b] 段之间就会存在一点，「以某个位置为起点」就会「更优」，分为下面两种情况：

2.1.4.1 证明过程：

（1）情况一：在 ab 段存在一个 c 点，从这个 c 位置开始，「不越过」的累加和比从 a 开始的累加和更优：(元素全为负数不考虑，因为全为负数时该贪心策略本身就是正确的)

如果存在这一点，那么 sum[c,k] > sum[a,k]，但是如果 sum[c,k] > sum[a,k]，那么 sum[a,c − 1] < 0，这与我们的贪心策略矛盾即在区间加上元素 b 之前，区间中任意以 a 为左端点的一个子区间区间和都大于 0。故该情况不成立的. （2）情况二：在 ab 段存在一个点 c，从这个位置开始，「越过 b 或者刚好在 b」的累加和比从 a 开始的累加和更优：

如果存在这一点，那么：sum[c,b] > sum[a,b]，但是如果 sum[c,b] > sum[a,b]，那么 sum[a,c − 1] < 0，与我们的贪心策略矛盾即在区间加上元素 b 之前，区间中任意以 a 为左端点的一个子区间区间和都大于 0。故该情况不成立的. 故证毕

2.2 纪念品分组

2.2.1 题目

链接：纪念品分组

2.2.2 算法原理

先将所有的纪念品排序，每次拿出当前的最小值 x 与最大值 y： （1）如果把 x+y ≤w：就把这两个放在一起； （2）如果 x+y >w：说明此时最大的和谁都凑不到一起，y 单独分组，x 继续留下在进行下一次判断。 直到所有的物品都按照上述规则分配之后，得到的组数就是最优解

2.2.3 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e4 + 10;
int a[N];
int main(){
    int n,w; cin >> w >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int l = 1, r = n;
    int ret = 0;
    while(l <= r)//相遇时给物品还未分配
    {
        if(a[l] + a[r] <= w){ l++; r--;}
        else r--;
        ret++;
    }
    cout << ret << endl;
    return 0;
}

2.2.4 贪心策略证明

（1）证明方法：交换论证法 （2）证明思路：对于区间 [ai…aj],如果存在最优解但是 ai 与 aj 的分配方式与我们贪心解的分配方式不一样，我们通过调整方式调整成贪心解

2.2.4.1 证明过程：

(1) a[i] + a[j] > w 时： 贪心解会把 a[j] 单独分组，a[i] 留待下次考虑. 最优解也必定会把 a[j] 单独分组，因为没有更小的 a[i] 值与 a[j] 组合。此时贪心解与最优解一致。 (2）a[i] + a[j] ≤ w 时： 贪心解会把两者组合分在一个组里面；最优解可能有以下几种情况 情况一： ◦a[j] 和 a[k] 和一组： ▪如果 a[i] 单独一组的话，a[j] + a[k] 为一组，可以调整交换 a[i] 和 a[k]，此时并不影响结，与贪心解一致 ▪如果 a[i] 和 a[l] 一组的话，交换 a[l] 和 a[k],就会变成 (a[i] + a[j])，(a[l] + a[k])，总体变成 a[l] + a[k] ≤ a[j] + a[k] ≤ w，不影响最终结果，和贪心解一致 情况二： ◦a[j] 单独一组： ▪如果 a[i] 也单独一组的话，最优解还不如贪心解分的组少，矛盾。 ▪如果 a[i] 和另一个 a[k] 组的话，我们可以把 a[k] 和 a[j] 交换，此时并不影响结，与贪心解一致

总之：综上所述，我们可以通过不断的「调整」，使的最优解在「不改变其最优性」的前提下，变得和贪心解一致。