贪心与证明
要选用贪心策略,就要先证明贪心策略是正确的,才能考虑使用。在很多情况下,贪心的合理性并不是显然的,但如果能找到一个反例,就可以证明这样的贪心不正确。
部分背包问题
部分背包问题
当背包问题的物品可以被任意切割的时候,贪心策略是正确的。这很好理解。只要拿单位价值最高的商品,填满袋子就是最优解。
ac代码:
#include <iostream>
#include <algorithm>
using namespace std;
int n, t;
const int N = 110;
struct Coin
{
double v;
double w;
double val;
bool operator<(const Coin& c) const
{
return val < c.val;
}
}coin[N];
int main()
{
cin >> n >> t;
for(int i = 0; i < n; i++)
{
double w, v;
cin >> w >> v;
coin[i] = {v, w, v / w};
}
sort(coin, coin + n);
double ans = 0;
for(int i = n - 1; i >= 0; i--)
{
if(t < coin[i].w)
{
ans += coin[i].val * t;
t = 0;
break;
}
else if(t > 0)
{
t -= coin[i].w;
ans += coin[i].v;
}
}
printf("%.2lf", ans);
}
但如何证明当背包问题物品无法被切割时,贪心策略是错误的呢?
可以用反证法,只要有一个例子可以证明贪心是错误的,那就不能用。(这个例子很好找,给的测试案例就是一个)
排队接水
有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为 Ti ,请编程找出这 n 个人排队的一种顺序,使得 n 个人的平均等待时间最小。
这道题凭直觉来看也很简单。平均等待时间最小,就是让接水时间长的人少人等,即接水时间越短的人越先接水。
其实不证明也行,可以举一些例子,如果举不出反例,就证明贪心正确。可以用暴力枚举来验证答案。如果暴力和贪心答案一致,那贪心正确性很高。
ac代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
struct P
{
int id, t;
bool operator< (const P& p) const
{
if(t == p.t) return id < p.id;
else return t < p.t;
}
}p[N];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int t;
cin >> t;
p[i] = {i , t};
}
sort(p + 1, p + n + 1);
double res = 0;
int u = n;
for(int i = 1; i <= n; i++)
{
res += p[i].t * (u - 1);
u --;
cout << p[i].id << ' ';
}
puts("");
printf("%.2lf", res / n);
}
凌乱的yyy/线段覆盖
线段覆盖
这是一道经典的贪心问题。就是给定n个区间,最多有几个区间是不重合不相交的。
思路:从左向右看,找到结束位置最靠左的。这样可以给后面的区间更多的空间放置。在这一步上是局部最优解。然后继续找最靠左的区间,能放就放(有可能区间虽然更靠左,但是有重叠,那就不能放了)。
这样就做到了每一步都是局部最优解,那就是全局最优解了。
因此我们只要按结束位置来升序排序即可。
ac代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
struct Contest
{
int begin, end;
bool operator< (const Contest& c) const
{
return end < c.end;
}
}contest[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
int b, e;
cin >> b >> e;
contest[i] = {b , e};
}
sort(contest, contest + n);
int ans = 0, end = -1;
for(int i = 0; i < n; i++)
if(contest[i].begin >= end)
{
ans++;
end = contest[i].end;
}
cout << ans;
}