貪心演算法的實現

1. 哈夫曼編碼（貪心演算法）

參考： 哈夫曼編碼

哈夫曼編碼是一種十分有效的編碼方法，廣泛應用於 數據壓縮 中
通過採用 不等長 的編碼方式，根據 字元頻率的不同 ，選擇 不差派拿同長度的編碼 ，對頻率 越高 的字元採用 越短 的編碼實現數據的高度壓縮。
這種對頻率越高的字元採用越短的編碼來編碼的方式應用的就是貪心演算法的思想。

下面看一個例子：
假如我們有虛搭一個包含1000個字元的文件，每個字元佔1個byte(1byte=8bits)，則存儲這100個字元一共需要8000bits。這還是有一些大的
那我們統計一下這1000個字元中總共有多少種字元，原來需要8bit來表示一個字元，如果使用更少的位數來表示這些字元，則可以減少存儲空間。
假設這1000個字元中總共有a、b、c、d、e、f共6種字元，使用使用3個二進制位來表示的話，存儲這1000個字元就只需要3000bits，比原來更節省存儲空間。

或許還可以再壓縮一下：
根據字元出現的 頻率 給與字元 不等長 的編碼，頻率越高的字元編碼越短，頻率越低的字元編碼越長。
它不能像等長編碼一樣直接按固定長度去讀取二進制位，翻譯成字元，為了能夠准確讀取翻譯字元，它要求一個字元的編碼不能是另外一個字元的前綴。

假設a、b、c、d、e、f這6個字元出現的頻率依次降低，則我們可以給與他們這樣的編碼

假如字元的出現頻率如圖所示，按照這樣的編碼表示的話，總位數如圖，一共2100bits，更加節省空間了

貪心策略：頻率小的字元，優先入隊。

步驟：
1.將每一個字元作為節點，以出現頻率大小作為權重，將其都放入 優先隊列 中（一個最小堆）；
2.每次出隊兩個節點並創建一個父節點，使其權值為剛剛出隊的節點的權值和，並且為兩個節點的父節點（合並）。然後將這個樹入隊。
3.重復操作2，直到隊列中只有一個元素（此時這個元素表示形式應該為一個樹）時，完成創建。

創建好了樹，該怎麼編碼呢？
我們對一個哈夫曼樹，從父節點開始的所有節點，往左邊標0，右邊標1。那麼到達葉子節點的順次編碼就可以找到了。

C：字元集合
Q：優先隊列
EXTRACT-MIN：傳入一羨山個隊列，出隊最小的元素
INSERT：將z插入到Q中

當for循環結束之後，此時隊列中只有一個元素，就是我們需要的哈夫曼樹，最後返回此樹即可。

假設T樹已經是一個最優的樹，假設x、y的頻率小於等於最低處的a、b，然後交換x、a，y、b。

計算代價是否發生變化。
比如這里比較 T 變成 T 』 後代價是否變化，發現代價變小或不變。

同理T』到T』』，又因為T本來假設就是最優的，所以只能相等
所以T』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的

2. 求一個演算法(貪心演算法)

貪心演算法

一、演算法思想

貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1. 不能保證求得的最後解是最佳的；
2. 不能用來求最大或最小解問題；
3. 只能求滿足某些約束條件的可行解的范圍。

實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；

二、例題分析

1、[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30

分析：

目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)

（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔重量最小的物品裝入是否能得到最優解？
（3）每次選取單位重量價值最大的物品，成為解本題的策略。 ?

值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
（1）貪心策略：選取價值最大者。反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
（3）貪心策略：選取單位重量價值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。

所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）

================================
三個經典的貪心演算法

有人說貪心演算法是最簡單的演算法，原因很簡單：你我其實都很貪，根本不用學。有人說貪心演算法是最復雜的演算法，原因也很簡單：這世上貪的人太多了，那輪到你我的份？

不論難度如何，貪心演算法都是一個很重要的演算法，我在網上N多Online Judge中的題目中，總結了三類較為常見，也十分經典的貪心演算法，發布在這兒Just For Fun。

（註：由於沒有現成的名字可用，這三種類型貪心演算法的名字都是我自己取的，如果你聽著別扭，請見諒。）

No 1.線段覆蓋（linescover）

題目大意：

在一維空間中告訴你N條線段的起始坐標與終止坐標，要求求出這些線段一共覆蓋了多大的長度。

解題思路：

將線段按其坐標進行排序（排序的具體方法:按起始坐標排，起始坐標相同的按終止坐標排，都是小在前大在後）,使之依次遞增，並按順序分別編號為X(i),X(i).a代表其起始坐標，X(i).b代表其終止坐標。

然後按排好的順序依次處理：定義一個變數last記錄考慮到當前線段之時被線段覆蓋的最大的坐標值，再定義一個變數length記錄當前線段覆蓋的長度。對於後面的線段，我們把它看成由兩個部分組成，即把它分成last之前的線段和last之後的線段。（如果線段全部處在last之後，其last之前的部分不存在。）由於我們排過序，我們可以肯定當前考慮的線段X(i)其處在last之前的部分不會對length造成影響（因為X(i-1).b=last，X(i).a>=X(i-1).a,即X(i)在last之前的部分所處位置肯定被線段X(i-1)覆蓋過），所以會對length產生影響的即是X(i)處在last之後的部分。

所以我們可以依次對每條線段做如下處理：（初始化length為零，last為負無窮）

length+=X(i).b-last (X(i).a<=last 且 X(i).b>=last)

length+=X(i).b-X(i).a (X(i).a>last)

last=X(i).b;

最後length就為我們所需要的答案。

No 2.最優數對（bestpair）

題目大意：

按遞增的順序告訴你N個正整數和一個實數P，要求求出求出該數列中的比例最接近P的兩個數（保證絕對沒有兩個數使得其比值為P）。

解題思路：

定義兩個指針i和j，先初始化i=j=1，然後進行如下操作：

當code[j]/code[i]>p時，inc（j）；

當code[j]/code[i]<p時，inc（i）。

記錄其中產生的最優值即為答案。

No 3.連續數之和最大值（maxsum）

題目大意：

給出一個長度為N的數列（數列中至少有一個正數），要求求出其中的連續數之和的最大值。（也可以加入a和b來限制連續數的長度不小於a且不大於b）。

解題思路：

先說不加限制的那種，定義一個統計變數tot，然後用循環進行如下操作：inc（tot，item） 其中如果出現tot<0的情況，則將tot賦值為0。在循環過程之中tot出現的最大值即為答案。

如果加入了限制條件的話，問題就變得難一些了（這句真的不是廢話）。為此我們先定義數組sum[i]來表示code[1]到code[i]之和（這樣的話code[a]~code[b]的和我們就可以用sum[b]-sum[a-1]來表示了。）。

再維護一個數組hash[i]來表示滿足條件的sum[a-1]的下標，並使之按遞增順序排列，這樣當前以第i的數為終止的數列的最大值肯定就是sum[i]-sum[hash[1]]。

現在我們來討論hash數組之中的數據需要滿足的條件和如何維護的具體問題：

當考慮到以第i個數為結尾時，hash[i]所表示的下標需要滿足的第一個條件就是題目規定的長度限制，我們需要實時的加入滿足長度規定的下標，刪除不符合要求的下標。其次，與不加限制條件時相同，若sum[i]-sum[hash[1]]的值小於零，則清空數組hash。

維護時可以這樣，當考慮到第i個數時，我們就將下標i-a+1加入到hash中，因為hash中原來已經排好序，因此我們我們可以用插入排序來維護hash的遞增性，然後我們考察hash[1]，若hash[1]<i-b+1，則證明其已超出長度限制，我們就將其刪除，接著再考慮更新後的hash[1],如此重復直至找到一個滿足條件的hash[1]為止。

我們可以用鏈表來表示hash，這樣就可以減少數據加入和刪除時頻繁數據移動的時間消耗。

記錄下sum[i]-sum[hash[1]]的最大值即為答案。

3. 貪心演算法 活動安排問題

這道題的貪心演算法比較容易理解，我就不多說明了，只是提到一下演算法思路1、建立數學模型描述問題。我在這里將時間理解成一條直線，上面有若干個點，可能是某些活動的起始時間點，或終止時間點。在具體一下，如果編程來實現的話，將時間抽象成鏈表數組，數組下標代表其實時間，該下標對應的鏈表代表在這個時間起始的活動都有哪些，具體參照程序注釋。2、問題分解。為了安排更多的活動，那麼每次選取佔用時間最少的活動就好。那麼從一開始就選取結束時間最早的，然後尋找在這個時間點上起始的活動，以此類推就可以找出貪心解。程序代碼：#include<stdio.h>
struct inode //自定義的結構體
{
int end; //表示結束時間
inode *next; //指向下一個節點的指針
};int main()
{
inode start[10001],*pt;
int a,b,i,num=0; //num負責計數，i控制循環，a，b輸入時候使用
for(i=0;i<10001;i++) //初始化
{
start[i].next=NULL;
}
while(scanf("%d %d",&a,&b)) //輸入並建立數據結構
{
if(a==0&&b==0) break;
pt=new inode; //創建新的節點，然後將該節點插入相應的位置
pt->end=b;
pt->next=start[a].next;
start[a].next=pt;
}
i=0;
while(i<10001) //進行貪心演算法，i表示當前時間
{
if(start[i].next==NULL)
{
i++; //該時間無活動開始
}
else
{
int temp=10001; //臨時變數，存儲該鏈表中最早的終止時間
for(pt=start[i].next;pt!=NULL;pt=pt->next)
{
if(pt->end<temp)
{
temp=pt->end;
}
}
i=temp; //將當前時間設置成前一子問題的終止時間
num++;
}
}
printf("%d\n",num); //列印結果
return 0;
}代碼並不一定是最快速的，但是可以求出貪心解，如果你做的是ACM編程題目，不保證能AC注釋我盡力寫了，希望對你有幫助。

4. 收集各類貪心演算法（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();
}

5. 貪心演算法的基本思路

1.建立數學模型來描述問題
⒉把求解的問題分成若干個子問題。
⒊對每一子問題求解，得到子問題的局部最優解。
⒋把子問題的解局部最優解合成原來解問題的一個解。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步
do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解。
下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。

6. 貪心演算法實現哈夫曼編碼

// 哈夫曼編碼(演算法)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char *HuffmanCode; //動態分配數組，存儲哈夫曼編碼

typedef struct
{
unsigned int weight; //用來存放各個結點的權值
unsigned int parent,LChild,RChild; //指向雙親、孩子結點的指針
} HTNode, *HuffmanTree; //動態分配數組，存儲哈夫曼樹

//選擇兩個parent為0，且weight最小的結點s1和s2
void Select(HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
if((*ht)[i].weight<(*ht)[min].weight) min=i;
}
}
*s2=min;
}

//構造哈夫曼樹ht。w存放已知的n個權值
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n)
{
int m,i,s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1; i<=n; i++) //1--n號存放葉子結點，初始化
{
(*ht)[i].weight=w[i];
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
}
for(i=n+1; i<=m; i++)
{
(*ht)[i].weight=0;
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
} //非葉子結點初始化
printf("\nHuffmanTree: \n");
for(i=n+1; i<=m; i++) //創建非葉子結點，建哈夫曼樹
{ //在(*ht)[1]~(*ht)[i-1]的范圍內選擇兩個parent為0
//且weight最小的結點，其序號分別賦值給s1、s2
Select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);
}
printf("\n");
} //哈夫曼樹建立完畢

//從葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i,start,p;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n個編碼的頭指針
cd=(char *)malloc(n*sizeof(char)); //分配求當前編碼的工作空間
cd[n-1]='\0'; //從右向左逐位存放編碼，首先存放編碼結束符
for(i=1; i<=n; i++) //求n個葉子結點對應的哈夫曼編碼
{
start=n-1; //初始化編碼起始指針
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //從葉子到根結點求編碼
if( (*ht)[p].LChild==c) cd[--start]='0'; //左分支標0
else cd[--start]='1'; //右分支標1
hc[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個編碼分配空間
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1; i<=n; i++)
printf("HuffmanCode of %3d is %s\n",(*ht)[i].weight,hc[i]);
printf("\n");
}

void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,i,n,wei,m;

printf("\nn = " );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
printf("\ninput the %d element's weight:\n",n);
for(i=1; i<=n; i++)
{
printf("%d: ",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
CrtHuffmanCode(&HT,&HC,n);
}

7. 找零錢問題 [貪心演算法](java實現）

public getMin{

public int MinNumber=0;

public int findMax(int[] a){
for(int i=0;i<a.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}

public boolean Compare(int a,int b){
public boolean flag=true;
if(a>b) flag=flase;
return flag;
}

public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];

int index=0;

for(int i=0;i<M.length;i++){
boolean f = this.Compare(M[i],money)
if(f) findM[index++]=M[i];
}

int max = this.findMax(findM);
MinNumber++;

if((Money-max)!=0) {
getMinNumber(M,Money-max)
}

return MinNumber;
}

public int[] Start(){
System.out.println("請輸入查詢組數");
int group=System.in.read();

int[] M={1,2,5,10,20,50,100};

int[] Result = new Int[group];
int index=0;

while (group-- > 0){
System.out.println("請輸入金額");
int money=System.in.read();
Result[index++] = getMinNumber(M,money);
MinNumber=0;
}
}

public void print(int[] MinNumber){
for(int i=0;i<MinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}

public static void main(String[] args){
new getMin().print(new getMin().Start());
}

沒測試啊，有問題請勿噴，呵呵