貪心演算法排隊

⑴ 排隊打水問題

Sample Input

3 2
1 2 3

Sample Output

7

3個人，2個水龍頭，3個人打水時間分別為1、2、3，那麼最少時間應該是3分鍾才對，怎麼會是7分鍾呢？

⑵ 貪心演算法：最小生成樹，霍夫曼編碼

連通圖： 在無向圖中，若任意兩個頂點vi與vj都有路徑相通，則稱該無向圖為連通圖。
強連通圖（Strongly Connected Graph） 是指在有向圖G中，如果對於每一對vi、vj，vi≠vj，從vi到vj和從vj到vi都存在路徑，則稱G是強連通圖。
連通網： 在連通圖中，若圖的邊具有一定的意義，每一條邊都對應著一個數，稱為權；權代表著連接連個頂點的代價，稱這種連通圖叫做連通網。
生成樹： 一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但只有足以構成一棵樹的n-1條邊。一顆有n個頂點的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環。
最小生成樹： 在連通網的所有生成樹中，所有邊的代價和最小的生成樹，稱為最小生成樹。
示例：
分別使用 Kruskal演算法 和 Prim演算法 ，找出下圖的最小生成樹。

使用變長編碼表對源符號（如文件中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字元串的平均長度、期望值降低，從而達到無損壓縮數據的目的。
具體步驟
1.將信源符號的概率按減小的順序排隊。
2.把兩個最小的概率相加，並繼續這一步驟，始終將較高的概率分支放在右邊，直到最後變成概率1。
3.畫出由概率1處到每個信源符號的路徑，順序記下沿路徑的0和1，所得就是該符號的霍夫曼碼字。
4.將每對組合的左邊一個指定為0，右邊一個指定為1（或相反）。
示例：
假設字元a,b,c,d,e出現的概率分別為1/2,1/4,1/8,1/16,1/16。
1.求出各字元哈夫曼編碼表。
2.假設一個文件有1,000,000個字元，求出編碼之後文件的位元組長度。

A:0
B:10
C:110
D:1110
E:1111
a所佔長度l1為：（1,000,000/2） 1
b所佔長度l2為：（1,000,000/4） 2
c所佔長度l3為：（1,000,000/8） 3
d所佔長度l4為：（1,000,000/16） 4
e所佔長度l5為：（1,000,000/16）*4
文件的總長度l = l1 + l2 + l3 + l4 + l5 = 1875000

⑶ 求解一貪心演算法問題

最快回答那個不懂別亂說，別誤人子弟。
這題標準的貪心演算法，甚至很多時候被當做貪心例題
要求平均等待時間，那麼就得用 總等待時間 / 人數
所以只用關心總等待時間，
如果數據大的在前面，那麼後面必然都要加一次這個時間，所以按從小到大排。
給你寫了個，自己看吧。
#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;
}

⑷ C語言演算法，用貪心法

貪心演算法雖然不是最好的，但畢竟是你要求的。。。
隨機取一個人，
循環開始：隨機取一個沒接水的人，
比較兩個人的接水時間大小，讓小的先接。
累加總等待時間為接水時間。
循環體結束。
輸出平均接水等待時間累加T/人數n

⑸ 排隊打水 pascal

type rtype=record
num,data:longint;
end;
var i,j,n:longint;
total:int64;
x:real;
a:array [1..10000] of rtype;

procere qsort(l,r:longint);
var i,j,mid:longint;
temp:rtype;
begin
i:=l; j:=r;
mid:=a[(i+j) div 2].data;
repeat
while a[i].data<mid do inc(i);
while a[j].data>mid do dec(j);
if i<=j then begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;

begin
assign(input,'water.in');
assign(output,'water.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
begin
read(a[i].data);
a[i].num:=i;
end;
readln;
qsort(1,n);
for i:=1 to n do
for j:=1 to i-1 do
total:=total+a[j].data;
x:=total/n;
for i:=1 to n do write(a[i].num,' ');
writeln;
writeln(x:0:2);
close(input);
close(output);
end.
其實很簡單，就是排序，因為前面時間越少等的越少

⑹ 求貪心演算法題（Pascal）

《編程之美》裡面有一道買書問題的貪心演算法。
題目是這樣的：
在節假日的時候，書店一般都會做促銷活動。由於《哈利波特》系列相當暢銷，店長決定通過促銷活動來回饋讀者。上櫃的《哈利波特》平裝本系列中，一共有五卷。假設每一卷單獨銷售均需8歐元 。如果讀者一次購買不同的兩卷，就可以扣除5%的費用，三卷則更多。假設具體折扣的情況如下：
本數 折扣
2 5%
3 10%
4 20%
5 25%
在一份訂單中，根據購買的卷數及本數，就會出現可以應用不同折扣規則的情況。但是，一本書只會應用一個折扣規則。比如，讀者一共買了兩本卷一，一本卷二。那麼，可以享受到5%的折扣。另外一本卷一則不能享受折扣。如果有多種折扣，希望計算出的總額盡可能的低。
要求根據以上需求，設計出演算法，能夠計算出讀者所購買一批書的最低價格。

⑺ 演算法09-貪心演算法

貪心演算法與動態規劃的不同在於它對每個子問題的解決方案都作出選擇，不能回退。動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。

很多情況下，可以在某一步用貪心演算法，全局再加一個搜索或遞歸或動態規劃之類

貪心法可以解決一些最優化問題，如:求圖中的最小生成樹、求哈夫曼編碼等。然而對於工程和生活中的問題，貪心法一般不能得到我們所要求的答案。
一單一個問題可以通過貪心法來解決，那麼貪心法一般是解決這個問題的最好辦法。由於貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助演算法或者直接解決一些要求結果不特別精確的問題。

當硬幣可選集合固定:Coins = [20,10,5,1],求最少幾個硬幣可以拼出總數。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面這些硬幣依次是後面硬幣的整數倍，可以用貪心法，能得到最優解，

貪心法的反例
非整除關系的硬幣，可選集合:Coins = [10,9,1],求拼出總數為18最少需要幾個硬幣？
最優化演算法:9 + 9 = 18 兩個9
貪心演算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八個1

簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。這種子問題最優解成為最優子結構。
貪心演算法與動態規劃的不同在於它對每個子問題的最終方案都作出選擇，不能回退。
動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多隻能給一塊餅干。
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅乾的最小尺寸；並且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，並輸出這個最大數值。
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由於他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應該輸出1。
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個演算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。
因為這樣屬於同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

給定一個非負整數數組 nums ，你最初位於數組的 第一個下標 。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最後一個下標。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然後再從下標 1 跳 3 步到達最後一個下標。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最後一個下標。

給定一個非負整數數組，你最初位於數組的第一個位置。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數到達數組的最後一個位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最後一個位置的最小跳躍數是 2。
從下標為 0 跳到下標為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。
說明:
假設你總是可以到達數組的最後一個位置。
移動下標只要遇到當前覆蓋最遠距離的下標，直接步數加一，不考慮是不是終點的情況。
想要達到這樣的效果，只要讓移動下標，最大隻能移動到nums.size - 2的地方就可以了。
因為當移動下標指向nums.size - 2時：
如果移動下標等於當前覆蓋最大距離下標， 需要再走一步（即ans++），因為最後一步一定是可以到的終點。（題目假設總是可以到達數組的最後一個位置），如圖：

如果移動下標不等於當前覆蓋最大距離下標，說明當前覆蓋最遠距離就可以直接達到終點了，不需要再走一步。如圖：

機器人在一個無限大小的 XY 網格平面上行走，從點 (0, 0) 處開始出發，面向北方。該機器人可以接收以下三種類型的命令 commands ：
-2 ：向左轉 90 度
-1 ：向右轉 90 度
1 <= x <= 9 ：向前移動 x 個單位長度
在網格上有一些格子被視為障礙物 obstacles 。第 i 個障礙物位於網格點 obstacles[i] = (xi, yi) 。
機器人無法走到障礙物上，它將會停留在障礙物的前一個網格方塊上，但仍然可以繼續嘗試進行該路線的其餘部分。
返回從原點到機器人所有經過的路徑點（坐標為整數）的最大歐式距離的平方。（即，如果距離為 5 ，則返回 25 ）
注意：
北表示 +Y 方向。
東表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
輸入：commands = [4,-1,3], obstacles = []
輸出：25
解釋：
機器人開始位於 (0, 0)：

在檸檬水攤上，每一杯檸檬水的售價為 5 美元。
顧客排隊購買你的產品，（按賬單 bills 支付的順序）一次購買一杯。
每位顧客只買一杯檸檬水，然後向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。
注意，一開始你手頭沒有任何零錢。
如果你能給每位顧客正確找零，返回 true ，否則返回 false 。
示例 1：
輸入：[5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那裡，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那裡，我們收取一張 10 美元的鈔票，並返還 5 美元。
第 5 位顧客那裡，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由於所有客戶都得到了正確的找零，所以我們輸出 true。
示例 2：
輸入：[5,5,10]
輸出：true
示例 3：
輸入：[10,10]
輸出：false
示例 4：
輸入：[5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那裡，我們按順序收取 2 張 5 美元的鈔票。
對於接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然後返還 5 美元。
對於最後一位顧客，我們無法退回 15 美元，因為我們現在只有兩張 10 美元的鈔票。
由於不是每位顧客都得到了正確的找零，所以答案是 false。

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
你可以認為每種硬幣的數量是無限的。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
示例 4：
輸入：coins = [1], amount = 1
輸出：1
示例 5：
輸入：coins = [1], amount = 2
輸出：2

⑻ pascal題目：游戲

這題也許是貪心演算法的一個簡單應用 。

一開始我是這么想的：

⑼ 5. 設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti，1<=i<=n。應如何安排n個顧客的服務次序才能

上面的 思路不錯

最優服務次序問題
一、問題描述：
設有n 個顧客同時等待一項服務。顧客i需要的服務時間為ti, 1≦i ≦n 。共有s處可以提供此服務。應如何安排n個顧客的服務次序才能使平均等待時間達到最小?平均等待時間是n 個顧客等待服務時間的總和除以n。
二、貪心選擇策略
假設原問題為T，而我們已經知道了某個最優服務系列，即最優解為A={t(1)，t(2)，…．t(n)}(其中t(i)為第i個用戶需要的服務時間)，則每個用戶等待時間為：
T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；
那麼總等待時問，即最優值為：
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)；
由於平均等待時間是n個顧客等待時間的總和除以n，故本題實際上就是求使顧客等待時間的總和最小的服務次序。
本問題採用貪心演算法求解，貪心策略如下：對服務時間最短的顧客先服務的貪心選擇策略。首先對需要服務時間最短的顧客進行服務，即做完第一次選擇後，原問題T變成了需對n-1個顧客服務的新問題T』。新問題和原問題相同，只是問題規模由n減小為n-1。基於此種選擇策略，對新問題T』，選擇n-1顧客中選擇服務時間最短的先進行服務，如此進行下去，直至所有服務都完成為止 。
三、問題的貪心選擇性質
先來證明該問題具有貪心選擇性質，即最優服務A中t(1)滿足條件：t(1)<=t(i)(2<i<n)。
用反證法來證明：假設t(1)不是最小的，不妨設t(1)>t(i)(i>1)。
設另一服務序列B=（t(i)，t(2)，…，t(1)…，t(n)）
那麼TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0
即TA>TB，這與A是最優服務相矛盾。
故最優服務次序問題滿足貪心選擇性質。
四、問題的最優子結構性質
在進行了貪心選擇後，原問題T就變成了如何安排剩餘的n-1個顧客的服務次序的問題T』，是原問題的子問題。
若A是原問題T的最優解，則A』={t(2)，…t(i)…t(n))是服務次序問題子問題T』的最優解。
證明：假設A』不是子問題T』的最優解，其子問題的最優解為B』，則有TB』<TA』，而根據TA的定義知，TA』十t(1)=TA。因此TB』+t(1)<TA』+t(1)=TA，即存在一個比最優值TA更短的總等待時間，而這與TA為問題T的最優值相矛盾。因此，A』是子問題T』的最優值。
從以上貪心選擇及最優子結構性質的證明，可知對最優服務次序問題用貪心演算法可求得最優解。
根據以上證明，最優服務次序問題可以用最短服務時間優先的貪心選擇可以達到最優解。故只需對所有服務先按服務時間從小到大進行排序，然後按照排序結果依次進行服務即可。平均等待時間即為TA/n。
五、演算法實現
由多處最優服務次序問題具有貪心選擇性質和最優子結構性質，容易證明演算法greedy的正確性。本演算法採用最短服務時間優先的貪心策略。首先將每個顧客所需要的服務時間從小到大排序。然後申請2個數組：st[]是服務數組，st[j]為第j個隊列上的某一個顧客的等待時間；su[]是求和數組，su[j]的值為第j個隊列上所有顧客的等待時間；
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;//循環分配顧客到每一個服務點上
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
六、演算法測試結果

七、演算法復雜性分析
程序主要是花費在對各顧客所需服務時間的排序和貪心演算法，即計算平均服務時間上面。其中，貪心演算法部分只有一重循環影響時間復雜度，其時間復雜度為O(n)：而排序演算法的時間復雜度為O(nlogn)。因此，綜合來看演算法的時間復雜度為O(nlogn)。
八、參考文獻
[1] 王曉東.計算機演算法設計與分析(第3版)[M]．北京：電子工業出版社,2007．
[2] 陳媛.《演算法與數據結構》[M],清華大學出版社, 第1版,2005.4.
[3] 王曉東.演算法設計與實驗題解 [M]．北京：電子工業出版社,2008．

附錄（程序代碼）
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
using std::vector;
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
void main()
{int n;//等待服務的顧客人數
int s;//服務點的個數
int i;
int a;
int t;//平均服務時間
vector<int>x;
cout<<"please input the num of the customer:"<<endl;
cin>>n;
cout<<"please input the num of the server:"<<endl;
cin>>s;
cout<<"please input the need service time of each customer:"<<endl;
for(i=1;i<=n;i++){
cout<<"No."<<i<<endl;
cin>>a;
x.push_back(a);
}
t=greedy(x, s);
cout<<"the least average waiting time is:"<<t<<endl;
}