贪心算法习题

1. 贪心算法问题

//身为大一菜鸟的我曾错了n次的题
//算法是从头开始扫过去，若当前扫到的数比下一个大，则删，删后回退到上一个未被删的数继续，直到删完指定数或扫到最后一个元素，若删不够指定的数，则此刻数组肯定是递增的，所以只要从后向前删至足够数量便行了

#include<iostream>
#include<string.h>
using namespace std;
char str[250];
int a[250];
int b[250];

int main(){
int i, len, k, l, r, c, t, f;
do{
f = 0;
cin >> str;
if (str[0] == '0')
break;
len = strlen(str);
cin >> k;
for (i = 0; i<250; i++){
a[i] = i + 1;
b[i] = i - 1;
}
c = 0;
l = 0;
for (r = 1; str[r] != '\0';){
if (c >= k)
break;
if (str[r] - str[l] >= 0){
l = a[l];
r = a[r];
}
else{
c++;
if (b[l] != -1){
a[b[l]] = r;
b[r] = b[l];
l = b[l];
}
else{
f = 1;
b[r] = -1;
a[0] = r;
l = a[l];
r = a[r];
}
}
}
t = r - 1;
for (; c<k; c++){
a[b[t]] = r;
t = b[t];
}
if (f == 0)
cout << str[0];
i = 0;
for (i = a[i]; i<len; i = a[i]){
cout << str[i];
}
cout << endl;
} while (1);
return 0;
}

2. 收集各类贪心算法（C语言编程）经典题目

举个例子,假如你买东西，老板需要找给你99分钱，他有上面面值分别为25分，10分，5分，1分的硬币（都是假如，不符合实际），他得找你3个25分，2个10分的，4个1分的才为最佳方案！
用贪心算法编写程序实现！
main()
{
int
i,a[5],b[4],c[4];
/*
define
the
type
of
the
money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please
input
you
money
(fen):\n");
scanf("%d",&b[0]);
for
(i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i];
/*take
n
25
off
and
money
left*/
c[i]=(b[i-1]-b[i])/a[i];
/*
n
*/
printf("%d
is
%d\n",a[i],c[i]);
}
getch();
}

3. 贪心算法的例题分析

例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//输出一个解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八个方位子结点ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//递归调用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判断是否越界}ElseFind(x,y);Writeln('Total:',total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

4. 计算题【用贪心算法求解付款问题】

不是
贪心得到的结果是 3元，1元，5角，1角

最优是一张三元，两张八角。

5. 求三四个贪心算法的例题（配源程序代码，要带说明解释的）！非常感谢

贪心算法的名词解释
http://ke..com/view/298415.htm

第一个贪心算法 （最小生成树）
http://ke..com/view/288214.htm

第二个贪心算法 （Prim算法）
http://ke..com/view/671819.htm

第三个贪心算法 （kruskal算法）
http://ke..com/view/247951.htm

算法都有详细解释的

6. 求C语言或c++的贪心算法的例题

比如：
int a=3,b=4,c;
c=a+++b;
将被解释为
c=(a++)+b;
而不会被解释为
c=a+(++b);
贪心算法的主要意义是从左至右依次解释最多的符号！

7. 请学算法的高手来打一下这个关于贪心算法解决问题的题目，谢谢！！

n1长度的L1 与n2长度的L2 合并需要n1+n2-1 次比较

构造带权的最优二叉树

赫夫曼最优二叉树算法

先构造k个只有顶点的二叉树 用权（每个序列的长度）依次标记k个二叉树

从中选出最小权标记的树进行合并直到所有序列合并结束

8. 求贪心算法题（Pascal）

《编程之美》里面有一道买书问题的贪心算法。
题目是这样的：
在节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。上柜的《哈利波特》平装本系列中，一共有五卷。假设每一卷单独销售均需8欧元 。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：
本数 折扣
2 5%
3 10%
4 20%
5 25%
在一份订单中，根据购买的卷数及本数，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望计算出的总额尽可能的低。
要求根据以上需求，设计出算法，能够计算出读者所购买一批书的最低价格。

9. 一道贪心算法题目 一个人买卖商品，每天必须选择买或者卖，开始他的

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊会做了私戳我啊

10. 请教一道贪心算法的题目

貌似用不到贪心吧？
要求最少需要多少辆汽车只需确定最多有多少个乘客同时在车上就成了
算法如下：
1，定义a[n][n]用于存储p(i,j), 则i行的和为i站上车的人数， j列的和为j站下车的人数；
2，任意站点i开车时乘客人数f(i)=f(i-1)-d(i)+u(i),其中d(i)表示下车人数，u(i)表示上车人数，明显f(0)=0；
3，从i=1开始到i=n-1结束，遍历， 得到最多乘车的乘客数目max， 需要的车数=max/30 向上取整。