类似中企动力的做网站的,临沂网络网站建设,哈尔滨市招标网,用ps怎么做网站导航条一.简单贪心 贪心法是求解一类最优化问题的方法#xff0c;它总是考虑在当前状态下局部最优(或较优)之后#xff0c;来使全局的结果达到最优(或较优)的策略。显然#xff0c;如果采取较优而非最优的策略(最优策略可能不存在或是不易想到)#xff0c;得到的全局结果也无法是…
一.简单贪心 贪心法是求解一类最优化问题的方法它总是考虑在当前状态下局部最优(或较优)之后来使全局的结果达到最优(或较优)的策略。显然如果采取较优而非最优的策略(最优策略可能不存在或是不易想到)得到的全局结果也无法是最优的。而要获得最优结果则要求中间的每步策略都是最优的因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法即假设策略不能导致最优解然后通过一系列推导来得到矛盾以此证明策略是最优的最后用数学归纳法保证全局最优。不过对平常使用来说也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪本身更难)因此一般来说如果在想到某个似乎可行的策略之后并且自己无法举出反例那么就勇敢地实现它。
1.组个最小数
给定数字0~9各若干个可以任意顺序排列这些数字但必须全部使用且使目标数字尽可能小当然0不能做首位比如输入两个0、两个1、三个5和一个8得到的最小数字就是100155858。 相信大家一下子就可以看出来策略先从1~9中选择不为0的最小数输出然后从0~9输出数字每个数字输出次数为其剩余个数。
策略正确的证明
首先由于所有数字都必须参与组合因此最后结果的位数是确定的。 由于最高位不为0则选一个尽可能小的数作为首位——最高位定理其余位数也应该从小到大输出~
教材上的实在是太抽象了好像有点错误这里博主自己写了一种
#include cstdio
#include vector
#include iostream
#include algorithm
using namespace std;int main() { vectorint V;for(int i1;i10;i){int temp0;cintemp;V.push_back(temp);}sort(V.begin(),V.end()); //直接排成升序 int flag0; //标记 for(int i0;i9;i)if(V[i]!0){int tempV[i];V[i]V[0];V[0]temp;flagi;//保存第一个不为0的位置 break; }for(int iflag1;i9;i) //找更小的头直接从flag下一位开始即可节省时间~ if(V[i]V[0]V[i]!0){int tempV[i];V[i]V[0];V[0]temp;}for(int i0;i9;i)coutV[i];
}
逻辑上没什么难度主要是要想清楚~
2.月饼库存
输入第一行输入N和MN位月饼的种类数目M位市场对月饼的需求总量接下来的两行均要输入N个数第一行的N个数分别对应当前种类的月饼全部卖出后可以挣多少而第二行的N个数对应当前月饼的总数量~要求输出在规定需求量下最高收入 试想一下你如果作为老板会怎么去“贪得无厌”很明显——只需要在有限的需求量中尽可能多的卖出单价最贵的月饼岂不是可以收货最多的营业额如下博主自己写的一种实现和教材上的也不太一样
#include cstdio
#include vector
#include iostream
#include algorithm
using namespace std;struct mooncake{double num; //总数 double income; //总收入 double price; //单价需要自己计算
}; int main() {int N,M;cinNM;vectormooncake V;for(int i1;iN;i) {mooncake temp;V.push_back(temp);}cout请输入数量endl;for(int i1;iN;i) {double num0;cinnum;V[i-1].numnum;}cout请输入总价endl;for(int i1;iN;i) {double income0;cinincome;V[i-1].incomeincome;}for(int i0;iN-1;i) V[i].priceV[i].income/V[i].num; //计算单价//按单价降序排列保证贵的尽可能多卖for(int i0;iV.size()-1;i){for(int ji;jV.size()-1;j) if(V[j].priceV[i].price) {mooncake temp;tempV[j];V[j]V[i];V[i]temp;}}for(int i0;iV.size()-1;i)cout单价第(i1)高的值为V[i].income V[i].price V[i].numendl;for(int i0;iN-1;i)coutV[i].numendl; int j0; //使用的下标 double count0; //总利润 while(M0) //当还有需求量时 {double doubt0;doubtM-V[j].num; //用M减去当前类型的额总量 if(doubt0)//减了以后M还有剩余{M-V[j].num;//当前种类全部卖出 countV[j].income;//直接总价相加 j;coutV[j].num;}else if(doubt0) //不够减这么多{countV[j].price*M;//剩余部分按照单价计算 break; } }cout最高利润值为countendl;return 0;
} 仔细品味上述中的whlie循环当M还不为0时——即还有需求量就卖最贵的月饼。按顺序一个一个卖如果当前需求量足以卖完当前种类的全部数量则直接累加总价如果不足以卖完当前的全部则有多少卖多少按照单价计算即可~
我们拿教材的测试用例测试一下
3 2018 15 1075 72 45 结果为94.50和标准答案一致~ 此外这里博主直接把排序写在main函数了写在独立的函数再调用对于结构体型的vector好像有点bug排序不太成功大家如果知道原因的话可以在评论区写出来~ 二.区间贪心
题干如下
对于这类题目只需要牢记——优先选择左端点大的区间 下面来说说为什么要这样做如上图不难发现为了保证尽可能多选当某个较长的区间包含了较短的区间我们肯定要先选择最短的区间这一点很好理解。 而对于上面这种情况比如1和2这种重叠的区间不难发现如果选了左端点最大的1区间只会占到9号位而选了2号区间则会占到8号位——这显然不符合贪心尽可能少花钱少花区间的思想因此要选得尽可能靠左这样右边空的会更多~如上我们手算可以看出来最多有4个不相交的。
教材上的代码
#include cstdio
#include algorithm
using namespace std;const int maxn110;
struct Inteval{int x,y; //开区间左右端点
}I[maxn]; bool cmp(Inteval a,Inteval b)
{if(a.x!b.x)return a.xb.x; //左端点从大到小排序 elsereturn a.yb.y; //左端点相同的按右端点从小到大排序
}int main() {int n;while(scanf(%d,n,n!0)){for(int i0;in;i)scanf(%d%d,I[i].x,I[i].y);sort(I,In,cmp); //排序区间 int ans1,lastXI[0].x;//ans记录总数lastX记录上一个被选择的区间的左端点 for(int i1;in;i){if(I[i].ylastX) //如果该区间右端点在lastX左边 {lastXI[i].x; //以I[i]作为新选中的区间 ans; //不相交的区间个数1 } }printf(%d\n,ans); } return 0;
}
不过博主还是不太喜欢原始数组下面给一种vector结构体版本
#include iostream
#include vector
#include algorithm
using namespace std;struct section{int x0;int y0;//x和y分别为左右端点
}; int main() {int n0;vectorsection V;cinn;for(int i1;in;i) //读入数据 {section temp;int x0,y0;cinxy;if(xy) //防止左端点大于右端点 {int temp1x;xy;ytemp1; }else if(xy) //若左右端点相同 {i-1; //则当前输入 不算cout不可以输入相同的左右端点endl; continue; //舍弃数据本次循环作废~ } temp.xx;temp.yy;V.push_back(temp);}//按要求排序区间优先级 for(int i0;iV.size()-1;i){for(int ji1;jV.size()-1;j){if(V[j].xV[i].x) //左端点越大越靠前{section tempV[j];V[j]V[i];V[i]temp;}else if(V[j].xV[i].xV[j].yV[i].y) //左端点相同的话右端点小的优先 {section tempV[j];V[j]V[i];V[i]temp;} }}cout顺序如下endl; for(int i0;iV.size()-1;i)coutV[i].x~V[i].yendl; int count1,lastXV[0].x;//count用来统计总数lastX是上一个符合条件的区间的左端点for(int i1;iV.size()-1;i)//直接从第二个区间开始 {if(V[i].ylastX) //如果当前区间的右端点不和上一个左端点相加满足题意 {lastXV[i].x;count;} } coutcountendl;return 0;
}
测试如下 总的来说贪心法是用来解决一类最优化问题并希望由局部最优策略来推得全局最优结果的算法思想。贪心算法适用的问题一定满足最优子结构的性质即一个问题的最优解可以由他的子问题的最优解有效地构造出来。显然不是所有问题都适合贪心法但是这并不妨碍贪心算法成为一个简洁、实用、高效的算法~
