貪心演算法無效的問題

① 什麼是貪心演算法，用實例分析貪心演算法是如何解決實際問題

比如： 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;
}