贪心算法无效的问题

① 什么是贪心算法，用实例分析贪心算法是如何解决实际问题

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

② Python贪心算法

所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优加以考虑，它所做出的仅仅是在某种意义上的局部最优解。下面让我们来看一个经典的例题。假设超市的收银柜中有1分、2分、5分、1角、2角、5角、1元的硬币。
顾客结账如果需要找零钱时，收银员希望将最少的硬币数找出给顾客，那么，给定需要找的零钱数目，如何求得最少的硬币数呢？这个找零钱的基本思路：每次都选择面值不超过需要找给顾客的钱最大面值的硬币。
我们可以从面值最大的硬币开始，然后依次递减（图1）。
首先定义列表d存储已有币值。并且定义d_num存储每种币值的数量。通过循环遍历的方法计算出收银员拥有钱的总金额并保存在变量S中，要找的零钱变量为sum。当找零的金_比收银员的总金额多时，无法进行找零，提示报错。要想用的钱币数量最少，我们从面值最大的币值开始遍历。这里也就是我们贪心算法的核心步骤。计算出每种硬币所需要的数量，不断地更新硬币个数与硬币面值，最终获得一个符合要求的组合（图2）。
贪心算法在对问题求解时，不是对所有问题都能得到整体最优解，也不是从整体上去考虑，做出的只是在某种意义上的局部最优解。从面值最大的硬币开始依次递减，寻找可用的方法。一般贪心算法并不能保证是最佳的解决方法，这是因为：总是从局部出发没有从整体考虑，只能确定某些问题是有解的，优点是算法简单。常用来解决求最大值或最小值的问题。来源：电脑报

③ 为什么贪心算法不能解0-1背包问题

贪心算法解决背包问题有几种策略：
(i)一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
(ii)另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
(iii)还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n=

④ 求教一道贪心算法的问题

貌似用不到贪心吧？
要求最少需要多少辆汽车只需确定最多有多少个乘客同时在车上就成了
算法如下：
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 向上取整。

⑤ C语言贪心算法的问题

#include <stdio.h>
#define n 7 //有多少个物品种类
struct goods //定义物品的各个属性
{
int x; //物品放入背包的重量
int order; //物品编号
int p; //物品总价值
int w; //物品总重量
};
int Strategy1(struct goods goods[],int m) //策略一：按物品重量降序装包
{
struct goods temp;
float value=0;
int i,j,k=0;
for(i=0;i<n-1;i++) //按照物品总价值降序排列（上面不是说要按重量排序吗？n怎么没定义？）
{
for(j=i+1;j<n;j++)
{
if(goods[j].p>goods[i].p)
{
temp=goods[i];
goods[i]=goods[j];
goods[j]=temp;
}
}
}
for(;k<n;k++) //开始装包
{
if(goods[k].w>m)
break;
goods[k].x=goods[k].w;
m-=goods[k].w; //（看程序m应该是重量限制吧！前三个装包已经超重了，第四个当然 就没法装包了啊）

value+=goods[k].p;
}
if(k<n)
{
goods[k].x=m;
value=((float)m/goods[k].w)*goods[k].p;
}
printf("这是策略一的结果:\n"); //输出结果
for(i=0;i<n;i++)
{
printf("商品%d有%f放入背包\n",goods[i].order,(float)(goods[i].x/goods[i].w));
}
printf("商品的总价值为%f",value);
return value;
}
void main()
{
float value1;
struct goods goods[7]={0,1,10,2,0,2,5,3,0,3,15,5,0,4,7,7,0,5,6,1,0,6,18,4,0,7,3,1};
int m=15;
value1=Strategy1(goods,m);

⑥ 贪心算法的例题分析

例题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就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

⑦ 贪心算法问题

//身为大一菜鸟的我曾错了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;
}

⑧ 关于贪心算法的问题，可以帮忙解答下吗

题主这个不是贪心是动态规划.....

算了直接给题主个code吧 原题在https://oj.leetcode.com/problems/triangle/

classSolution{
public:
	intminimumTotal(vector<vector<int>>&triangle){
		intn=triangle.size();
		intm=triangle[n-1].size();
		vector<int>dp[2];
		for(inti=0;i<m;i++){dp[0].push_back(0);dp[1].push_back(0);}
		intpos=0;
		intresult=triangle[0][0];
		dp[0][0]=triangle[0][0];
		for(inti=1;i<n;i++){
			result=INT_MAX;
			for(intj=0;j<=i;j++){
				dp[1-pos][j]=INT_MAX;
				for(intk=-1;k<=0;k++){
					if(j+k<0||j+k>i-1)
						continue;
					dp[1-pos][j]=min(dp[1-pos][j],triangle[i][j]+dp[pos][j+k]);
				}
				result=min(result,dp[1-pos][j]);
			}
			pos=1-pos;
		}
		returnresult;
	}
};

⑨ 求解一贪心算法问题

最快回答那个不懂别乱说，别误人子弟。
这题标准的贪心算法，甚至很多时候被当做贪心例题
要求平均等待时间，那么就得用 总等待时间 / 人数
所以只用关心总等待时间，
如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。
给你写了个，自己看吧。
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i < n; ++i)
cin >> arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i < n; ++i)
{
tmax += tnow;
tnow += arr[i];
}
for(int i = 0; i < n; ++i)
{
printf("%0.2f ", arr[i]);
}
cout << endl;
printf("%0.2f\n",tmax / (float)n);
return 0;
}