貪心演算法解決生活中的問題

⑴ 貪心演算法的實際問題解決

均分紙牌 #include<cstdio>#include<iostream>#include<cstdlib>inta[1000];usingnamespacestd;intf(intn){intave=0;intf=0;for(inti=1;i<=n;i++){f=f+a[i];}returnf/n;}intmain(){intn;intans=0;intave;scanf(%d,&n);for(inti=1;i<=n;i++){scanf(%d,&a[i]);}ave=f(n);for(inti=1;i<=n;i++){if(a[i]==ave){continue;}if(a[i]!=ave){a[i+1]+=a[i]-ave;ans++;}}printf(%d,ans);return0;}

⑵ 貪心演算法解決特殊0-1背包問題

void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]為每個物品的重量，c為背包容量
{
int i;
for(i=1;i<=n;i++) x[i]=0;
for(i=1;i<=n;i++)
{
if(w[i]>c) break;
x[i]=1;
c-=w[i];
}
}

⑶ 用貪心演算法能求解背包問題嗎為什麼,理由是什麼

一般的貪心策略都會造成解的丟失,動態規劃則是相當於枚舉了所有的解.

如果你有一個很好的貪心策略,背包問題也能用貪心策略來解決.但是,你是很難找到一個很好的貪心策略的.

⑷ 為什麼貪心演算法不能解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=

⑸ 用貪心演算法解決背包問題

用貪心演算法解決背包問題，首先要明白，結果不一定是全局最優的。對於貪心法而言，首先步驟是找到最優度量標准，我這里的演算法採用的最優度量標準是： 收益p/重量w 的值最大者優先放入背包中，所以有演算法如下：void GreedyKnapsack(float * x){ //前置條件：w[i]已按p[i]/w[i]的非增次序排列 float u=m; //u為背包剩餘載重量，初始時為m for(int i=0;i<n;i++) x[i]=0; //對解向量x初始化 for(i=0;i<n;i++){ //按最優度量標准選擇的分量 if(w[i]>u) break; x[i]=1.0; u=u-w[i]; } if(i<n) x[i]=u/w[i];}

⑹ 貪心演算法可以解決0-1背包問題嗎

這種規則，價值最大的物品首先被裝入（假設有足夠容量），然後是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，考慮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], 比最優解

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

比如： int a=3,b=4,c; c=a+++b; 將被解釋為 c=(a++)+b; 而不會被解釋為 c=a+(++b); 貪心演算法的主要意義是從左至右依次解釋最多的符號！

⑻ 為什麼貪心演算法可用於解決最優化問題

最優化問題是程序設計中一類非常重要的問題。每一個最優化問題都包含一組約束條件和一個優化函數，滿足約束條件的問題求解方案稱為問題的可行解，使優化函數取得最優值的可行解稱為問題的最優解。貪婪演算法是解決最優化問題的一種基本方法。
它採用逐步構造最優解的思想，在問題求解的每一個階段，都作出一個在一定標准下看上去最優的決策；決策一旦作出，就不可再更改。制定決策的依據稱為貪婪准則。

⑼ 請問各位大蝦:怎樣用貪心演算法解決背包問題

貪心只能解決物品可以分割的背包問題，01背包得用動態規劃求解