贪心算法初步_奶牛塔c++
赞
踩
一.什么是贪心算法
贪心算法的定义：贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键在于贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法解题的一般步骤是：
1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一个子问题求解，得到子问题的局部最优解；
4. 把子问题的局部最优解合成原来问题的一个解。
———————————————————————————————————————————
通俗地说：
贪心算法是运用排序的一种算法。其主要功能是实现贪心思想（尽可能多获取）。
为什么说是依赖排序的一种算法呢？请随我看一道简单的题目。
题目描述
Farmer John最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。
所有N(1 <= N <= 20,000)头奶牛都有一个确定的身高H_i(1 <= H_i <= 10,000)。设所有奶牛身高的和为S。书架的高度为B，并且保证 1 <= B <= S < 2,000,000,007。
为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。
显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。
输入格式
- 第1行: 2个用空格隔开的整数：N 和 B * 第2..N+1行: 第i+1行是1个整数：H_i
输出格式
- 第1行: 输出1个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部
输入输出样例
输入 #1
6 40 6 18 11 13 19 11输出 #1
3说明/提示
输入说明:
一共有6头奶牛，书架的高度为40，奶牛们的身高在6..19之间。
输出说明:
一种只用3头奶牛就达到高度40的方法：18+11+13。当然还有其他方法，在此不一一列出了。
（来源于[USACO07DEC]Bookshelf B - 洛谷）
思路详解：
本题是一个经典的贪心，排序（推荐sort）后，再用for语句从后往前调用身高，将身高累加。最后在身高大于书架高度（h）时，输出用了几只羊，之后 return 0；
为了让大家更好的理解本思想，请看下面的表格：
| 3 | 1 | 4 | 9 | 8 | 5 | 6 | 3 | 1 | 1 |
| 1 | 1 | 1 | 3 | 3 | 4 | 5 | 6 | 8 | 9 |
h=30
第一行：原来的奶牛高度数组
第二行：排序后的奶牛高度数组
“思路详解”中，提到 用for语句从后往前调用身高 ，在表格中的意思就是
分别调用9，8，5，5 ······
从后往前调用的原因是：越往后，身高越大，身高越大，则奶牛总数量越小。
- for(int i=n;i>=1;--i){ //注意，是从后往前呦
- answer+=num[i];
- }
-
- //其中，n为奶牛数量，answer为累加高度，num为存放身高的数组
- //抱歉，本蒟蒻只会C++
题解（C++）
- #include<iostream>
- #include<cstdio>
- using namespace std;
- int main()
- {
- long long n,h,b,a[20001],ans=0,c=0;
- cin>>n>>h;
- for(int i=1;i<=n;++i){
- cin>>a[i];
- }
- sort(a+1,a+n+1);
- for(int i=n;i>=0;--i){
- ans=ans+a[i];
- c++;
- if(ans>=h)
- {
- cout<<c;
- return 0;
- }
- }
- return 0;
- }
你可能已经对贪心有了一定的了解，下面介绍一些更加难的贪心思想和题目。
贪心算法并不是对所有问题都能得到整体最优解，关键是贪心的策略的选择，选择的贪心策略 必须具备无后效性，即某个状态以前的过程不会影响以后的状态。之与当前状态有关。首先需要证明贪心策略是正确的，才可以考虑用贪心算法来解决该问题。在很多情况下，贪心的合理性并不是显然的，但如果能找到一个反例，就可以证明这样贪心不正确。
题目描述
阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N \le 100)N(N≤100) 堆金币，第 ii 堆金币的总重量和总价值分别是 m_i,v_i(1\le m_i,v_i \le 100)mi,vi(1≤mi,vi≤100)。阿里巴巴有一个承重量为 T(T \le 1000)T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？
输入格式
第一行两个整数 N,TN,T。
接下来 NN 行，每行两个整数 m_i,v_imi,vi。
输出格式
一个实数表示答案，输出两位小数
输入输出样例
输入 #1复制
4 50 10 60 20 100 30 120 15 45输出 #1复制
240.00
分析 因为包的称重量有限，如果能拿走相同重量的金币，当然是先拿走单位价格最贵的金币（性价比最高）。所以正确的做法是将金币的单价从高往低排序，然后按照顺序，将整堆金币放入包里。如果整堆放不进背包，就将这一堆金币分割到刚好能装下为止。
代码如下：
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- using namespace std;
- struct Item {
- int c, w;
- };//定义结构体，c代表价值，w代表重量
- Item item[1010];
- bool cmp(Item a, Item b){
- return a.w * b.c > b.w * a.c;
- }//排序函数，说白了就是比性价比
- int main() {
- int N, V;
- cin >> N >> V;
- for (int i = 1; i <= N; i++) {
- cin >> item[i].c >> item[i].w;
- }
- sort(item + 1, item + N + 1, cmp);//输入后排序
- double ans = 0;
- for(int i=1; i<=N; i++){
- if(V <= item[i].c){
- ans += (double)item[i].w / item[i].c * V;//因为上面结构体定义的w是int不是double，前面一定加(double)或1.0 * 。
- V = 0;
- break;//如果背包容量不够放下所有这种金币，就把背包装满，然后break。
- }
- else{
- ans += item[i].w;
- V -= item[i].c;
- }//够的话全装进去
- }
- printf("%.2lf", ans);//保留2位小数输出
- return 0;
- }
假设承重量是50，有四个金块，其重量和分别是：①（10，60） ②（20，100） ③（30，120） ④（15，45）。按照贪心策略，优先将单价高的金块装进背包，如果空间不够就跳过，继续考察剩下的金块，直到不能装下为止。以下表格所示为背包里面的几种情况。
重量 价值 单价
| ① | 10 | 60 | 6 |
| ② | 20 | 100 | 5 |
| ③ | 20 | 80 | 4 |
（a）总价：240
| ① | 10 | 60 | 6 |
| ② | 20 | 100 | 5 |
| ③ | 15 | 45 | 3 |
（b）总价：205
| ② | 20 | 100 | 5 |
| ③ | 30 | 120 | 4 |
（c）总价：220
贪心：利益最大化。
推荐几个题目，自己练习：
排队接水 - 洛谷
https://www.luogu.com.cn/problem/P1223【深基12.例1】部分背包问题 - 洛谷https://www.luogu.com.cn/problem/P2240凌乱的yyy / 线段覆盖 - 洛谷https://www.luogu.com.cn/problem/P1803数列分段 Section I - 洛谷https://www.luogu.com.cn/problem/P1181[NOIP2010 普及组] 接水问题 - 洛谷https://www.luogu.com.cn/problem/P1190爱与愁的心痛 - 洛谷https://www.luogu.com.cn/problem/P1614烦恼的高考志愿 - 洛谷https://www.luogu.com.cn/problem/P1678记得点赞加关注，再见，拜拜！！！
