贪心入门引例
| [日期：2021-03-11] | 作者：信息技术 次浏览 | [字体：大 中 小] |
贪心入门引例（一）--------简单最优装载问题
问题描述：
1. 我们有n个物体（每个物体重量不等）
2. 我们有一个包, 里面只能放重量总和为c的物品。
请问怎么放能使 物品最多 ?
解题思路： “ 这个很容易想到我们挑的东西越小，最后包里的物品数就越多 ”
所以我们：首先使用一个“ 结构体数组a[N] ” 记录下这些物体分别对应的序号index和重量w, 然后按照 重量w 从小到大排序( 注意序号不能打乱） 最后,按照排好序的数组。一个一个放进包里直到放不下为止。
程序代码：
//最优装载
#include<iostream>
#include<algorithm>
#define N 100
using namespace std;
struct Node{
int index;//第index件物品
int w;//物品的重量
};
bool cmp(const Node &a,const Node &b){
return a.w<b.w;
}
int main(){
Node a[N];
int n,c;
cin>>n; //输入初始可选物品总数
cin>>c;//输入背包的容量
for(int i=0;i<n;i++){
cin>>a[i].w;
a[i].index=i+1;
}
sort(a,a+n,cmp); //将所有物品按重量递增排序
int sum=0; //sum用于统计背包里的物品总数。
for(int i=0;i<n;i++){
if(c-a[i].w>=0){ //判断背包是否还装的下当前物品
cout<<"选择重为"<<a[i].w<<"的第"<<a[i].index<<"号物品"<<endl;
c-=a[i].w; //将物品放入背包里后背包容量减少。
sum++;
}
else{
break;
}
}
cout<<"包里有"<<sum<<"件物品"<<endl;
return 0;
}
实例测试+运行结果：
贪心入门案例（二）------部分背包问题
部分背包问题
有n个物品 ，但物品不仅仅只有重量w ,还有价值V，背包的重量上限还是c ， 要使放进背包的物品的重量不超过c的情况下价值总和最大。 【注】物品可以拿一部分并且这部分的重量和价值就按照比例计算。
首先，目标要求价值总和最大，我们很容易想到每次先拿价值最大的。但这样没有考虑到背包的重量这个条件。又因为物品可以按比例取，我们不难想到按照每个物品的“单位重量所含的价值==
价值/重量 ”来排序。
然后，我们就按照顺序将单位重量下价值更高的物品整体全部拿走,直到，后来我们的背包所剩余的容量已经不足以放下整个物品了, 那我们就把这最后一个物品拆分只拿走部分,这样我们就填满了背包
(可以注意到此题只要物品总和比背包容量大,背包总是可以被填满)。
#include<iostream>
#include<algorithm>
#define N 100
using namespace std;
struct Node{
int index; //第index件物品
int w; //物品的重量
int v; //物品的价值
double cp; //单位重量下物品的价值，为了等会比较是更准确，设置为double型
};
bool cmp(const Node &a,const Node &b){
return a.cp>b.cp; //根据物体的单位重量的价值由大到小排序
}
int main(){
Node a[N];
int n,c;
cin>>n; //输入初始可选物品总数
cin>>c;//输入背包的容量
for(int i=0;i<n;i++){
cin>>a[i].w;
a[i].index=i+1;
}
for(int i=0;i<n;i++){
cin>>a[i].v;
a[i].cp=(double)a[i].v/a[i].w;
}
sort(a,a+n,cmp); //将所有物品按单位重量的价值递减排序
int number;//number用于统计背包里的物品总个数
double sum=0; //sum用于统计背包里的物品总价值。
for(int i=0;i<n;i++){
if(c-a[i].w>=0){ //判断背包是否还装的下当前物品
cout<<"选择单位重量价值为"<<a[i].cp<<"的第"<<a[i].index<<"号物品"<<endl;
c-=a[i].w; //将物品放入背包里后背包容量减少。
sum+=a[i].v;
number++;
}
else{
printf("选择单位重量价值为%.2f的第%d号物品de一部分\n",a[i].cp,a[i].index);
sum+=(c*a[i].cp);
number++;
break;
}
}
cout<<"背包里一共装有"<<number<<"件物品"<<endl;
cout<<"背包里的价值总和为"<<sum<<endl;
return 0;
}
贪心入门案例（三）---------乘船问题
问题描述：
有n个人想要坐船去对岸, 每个人都有重量但不一定相等
现在有无数多船,所有船都有一个固定的最大承载量c 每条船最多只能坐2个人。
请问怎么分配能使用最少的船只使所有人都过河?
首先，我们很容易想到最重的与最轻的匹配，充分利用空间,的确.只要我们先找到最轻的人,然后看看他和最重的人可不可以共乘一条船：
1. 若可以,直接最重的与最轻的乘坐一艘。然后在剩下的人中再将最轻的与最重的匹配，看是否两人的体重和小于c，满足条件直接乘船走，重复执行此步，若不满足进行下面操作:
2.如果不行,最重的只能自己一艘船（最轻的都不行其他体重更不行）。然后，最轻的与第二重的人匹配，如果还是不行，那就给第二重的单独分配一条船，再继续与第三重的匹配看是否两人体重和超过c，，，，一直重复判断，，，直到最轻的人找到了匹配的小伙伴为止，乘坐一艘船离开。
#include<iostream>
#include<algorithm>
#define N 100
using namespace std;
int main(){
int a[N];
int n,c;
cin>>n; //输入初始可选物品总数
cin>>c;//输入背包的容量
for(int k=0;k<n;k++){
cin>>a[k];
}
sort(a,a+n);
int sum=0;//sum用于统计船数
int i=0,j=n-1;
while(i<=j){
if(i==j){ //i=j说明就剩一个人了，只能孤零零的自己离开
sum++;
printf("体重为%d的小可怜自己走啦~\n",a[i]);
break;
}
if(a[i]+a[j]<=c){
sum++; //小胖和小瘦一起走了
printf("体重为%d和体重为%d的走啦~\n",a[i],a[j]);
j--;
i++;
}
else{
printf("体重为%d的小胖胖自己走啦~\n",a[j]) ;
j--; //最重的人自己乘个小破船走了
sum++;
}
}
cout<<"一共需要"<<sum<<"艘小破船"<<endl;
return 0;
}
测试案例+运行结果：
贪心入门案例（四）-删数问题！
所谓贪心算法，当然是很贪心的算法。就是鼠目寸光地从局部看全局，首先得到局部的最优解，从而推导出全局的最优解。但是这种算法有时候并不适用，乱用会导致进入误区
例如这一道题：
在一个长n宽m的矩形中，有n*m数，若要从左下角走到右上角，且只能向右或向上走，问经过的数字之和最大是多少。
利用贪心的思想：从1开始，有两条路——2或3，因为2<3，所以选3,然后4、6。总和为14，最大。
|
3 |
6 |
|
2 |
4 |
|
1 |
3 |
但有这样一个例子：可见贪心算法为了3-2得到的1舍去了去10的道路，14<1+2+10+6，真不愧是“贪心”算法啊！
|
10 |
6 |
|
2 |
4 |
|
1 |
3 |
好了，介绍的都介绍完了。接下来我们进入正题——删数问题！
有一个长度为n（n <= 240）的正整数，从中取出s（s < n）个数，使剩余的数保持原来的次序不变，求这个正整数经过删数之后最小是多少。
输入：178543 4
样例输出：13
那么刚拿到这道题如何去思考呢？我们可以先试着找规律。
如果要从178543中取出1个数，使这个数最小，应该取……
8
如果要从17543中取出1个数，使这个数最小，应该取……
7
如果要从1543中取出1个数，使这个数最小，应该取……
5
……
可以发现：1，7，8是一个不降序数列（有相等的升序），也就是逐渐变多，而8，5，4，3是一个不升序数列（有相等的降序），逐渐减少。
8正好是升序数列的最后一个，也是降序数列的第一个。
其他几组也是同样的道理。
那么这样就好办了！我们只需要找到第一个升序数列的末尾并取出它就可以算成功完成了“局部的最优解”，再通过这个继续取出更多的数，直到取出s个数来，从局部的最优解进阶到全局的最优解，这一道题就完成了！
以下为参考程序：
#include<cstdio>
#include<cstring> //格式化输入输出头文件和字符串头文件
char n[250]; //利用字符数组来储存高精度数
int s,i,len,flag=1;
Int main()
{
scanf("%s %d",n,&s);
len=strlen(n); //这里是长度函数，取n的长度并赋值给len
while(s!=0) //只要s不是0，取数的工作就没有做完！
{
i=0;
while(n[i]<=n[i+1]) //括号内的条件保证了不降序的条件，当它退出时，就是升序数列的末尾了
i++;
while(i<len-1) //这时已经找到了要取出的数——n[i]，这是取出的过程
{n[i]=n[i+1];i++;} //其实这个循环可以用erase(i,1);代替
len--; //取出后数字长度减1
s--; //消耗掉一次取出次数
}
for(int i=0;i<len;i++) //输出时要小心最高位是0的问题！处理输出……
{
if(n[i]=='0'&&i<len-1&&flag==1) //如果即将输出的这一位是0且是最高位而且不是最后一个
continue; //跳过
else
{printf("%c",n[i]);flag=0;}//输出并且明确n[i]不再是最高位
}
return 0;
}
或如下
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
char a[101]; // 表示n位正整数a
int k; // k表示要删掉的数字的数量
cin>>a>>k;
int len,i; // len表示整数a的总位数，i表示第几位数
while(k>0){ // 当需要删除的数字大于0 时
i = 0; // 从第一位的位数开始
len = strlen(a);
while(i<len&&a[i]<=a[i+1]) //在保证不超出总位数且前一位数大于后一位数的情况下
i++; // 最后循环结束，得到一个递增的前i位数
while(i<len)
{
// 此时若i小于len，说明出现前一位大于后一位的情况
a[i]=a[i+1]; // 那么将后一位小的数字覆盖前一位大的数字
i++;
}
k--; // 需要删除的总数字数减少
}
i=0;
len = strlen(a);
while(a[i]=='0'&&i<len) i++; // 防止出现多个0的情况
if(i==len) cout<<'0'; // 防止整数a全被删除
else
{
for(i=i;i<len;i++)
cout<<a[i];
}
return 0;
}
删数问题2：
例如：148543 4
样例输出 13
首先，我们来分析一下样例：样例说要删去4个数，首先，我们第一直觉就是把最大的数删掉，于是我们删掉了8，接着我们依次把5、4、4删去，就达到了题目的目的。
但是，不要以为这就可以了贪心问题一般都十分恶心 ，我们再来看一组数：
如果有一个数是1439，要删一个数，按照我们刚刚的的思路，就是先把9删去，得到了143，可是如果我们把4删去，就得到了139，明显143> 139，所以我们还要进行一个判断，就是说如果一个数的第x个数位上的数是大于第x-1上数位的数的，那么，我们就要把在第x个数位上的数删去，比如说1879，我们要先删去8而不是9。
这样的话，我们就可以得到如下代码：
#include<bits/stdc++.h>
using namespace std;
string a;//输入高精度的数
int n,maxn=-100,maxn1=-100;
int main()
{
int x=1;
cin>>a>>n;//输入
while(x<=n)//判断有没有删到最大限度
{
for(int i=0;i<a.length();i++)
{
if(a[i]-'0'>maxn)
{
maxn=a[i]-'0';//枚举最大值
}
}
for(int i=0;i<a.length();i++)
{
if(a[i]-'0'>a[i+1]-'0')
{
maxn1=i;//判断前一个数位的数是否大于后一个数位的数
break;
}
}
for(int i=0;i<a.length();i++)
{
if(a[i]-'0'==maxn && i>maxn1)//如果最大值的位置大于上述的数（即前一个数位的数大于后一个数位的数）
{
a.erase(i,1);//删掉字符串中的最大值
break;
}
else//否则
{
a.erase(maxn1,1);//删掉上述的数
break;
}
}
x++;
maxn=-100;//更新最大值
}
cout<<a;
return 0;
}
但是这样还不够
我们发现如果说要删掉10020中的一个数，我们肯定删1，得到20，但是如果按照上面的程序跑的话，则会输出0020，所以我们要想办法再删完数后去掉前导零
while(a.size()-1!=0 && a[0]=='0')//枚举前导零
{
a.erase(0,1);
}
把这段代码加入程序中即可、
完整代码
#include<bits/stdc++.h>
using namespace std;
string a;
int n,maxn=-100,maxn1=-100;
int main()
{
int x=1;
cin>>a>>n;
while(x<=n)
{
for(int i=0;i<a.length();i++)
{
if(a[i]-'0'>maxn)
{
maxn=a[i]-'0';
}
}
for(int i=0;i<a.length();i++)
{
if(a[i]-'0'>a[i+1]-'0')
{
maxn1=i;
break;
}
}
for(int i=0;i<a.length();i++)
{
if(a[i]-'0'==maxn && i>maxn1)
{
a.erase(i,1);
break;
}
else
{
a.erase(maxn1,1);
break;
}
}
x++;
maxn=-100;
}
while(a.size()-1!=0 && a[0]=='0')
{
a.erase(0,1);
}
cout<<a;
return 0;
}
有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？
【算法分析】
由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，就不再赘述），所以这道题可以用贪心法解答，基本步骤：
(1)将输入的时间按从小到大排序；
(2)将排序后的时间按顺序依次放入每个水龙头的队列中；
(3)统计，输出答案。
【样例输入】
4 2 //4人打水，2个水龙头
2 6 4 5 //每个打水时间
参考程序主要框架如下：
cin>>n>>r;
memset(s,0,sizeof(s)); //初始化
j=0; minx=0;
for (i=1;i<=n;++i) //用贪心法求解
{
j++;
if (j==r+1) j=1; //前r个人为一组，第r+1个人回到第一个水龙
s[j]+=a[i]; //加上等待时间
minx+=s[j];
}
cout<<minx; //输出解答