㈠ 貪心演算法 活動安排問題
這道題的貪心演算法比較容易理解，我就不多說明了，只是提到一下演算法思路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注釋我盡力寫了，希望對你有幫助。
㈡ ACM題目 computer 最短作業優先
用貪心演算法吧，每次把當前可process的任務中剩餘工作時間最少的拿出來做。
用一個循環模擬cpu，每循環一次代表一個單位的時間。全局維護一個未完成任務的有序列表Q，按任務的剩餘工作時間排序。
每次循環中：
1、將該時間release的任務加入等待列表Q，排序。
2、將Q中的最小者的剩餘工作時間減1，代表該時間單位cpu
process該任務，如果減到0則記錄該任務結束時間。
㈢ ACM求大神 在線等
貪心演算法，先把輸入的數據按 W/P （即每錢黃金重量最大的來排）。然後從頭遍歷，如果錢夠付就全部賣下來，最後一個不夠就切塊。
下面代碼，我用了內部的qsort函數，
#include<stdio.h>#include<stdlib.h>struct Gold{ int nW; int nP; double dAve; };Gold Ggold[2001]; int cmp(const void *e1,const void *e2){ return( ((Gold*) e1)->dAve < ((Gold *) e2) ->dAve ); }int main(){ int nH,nK; while(scanf("%d%d",&nH,&nK)!=EOF) { if(nH==0&&nK==0) break; int i; for(i=0;i<nH;i++) { scanf("%d%d",&Ggold[i].nW,&Ggold[i].nP); Ggold[i].dAve=Ggold[i].nW*1.0/Ggold[i].nP; } qsort((void*)Ggold,nH,sizeof(Ggold[0]),cmp); // for(i=0;i<nH;i++) printf("%d %d %f\n",Ggold[i].nW,Ggold[i].nP,Ggold[i].dAve); double dSum=0; for(i=0;i<nH;i++) { if(nK>=Ggold[i].nP) { dSum+=Ggold[i].nW; nK-=Ggold[i].nP;} else { dSum+=nK*Ggold[i].nW*1.0/Ggold[i].nP; break; } } printf("%.3f\n",dSum); } return 0; }
希望能解決您的問題。
㈣ 浙大ACM第2416我用貪心演算法做的為什麼不對，希望高手解答
它的這個input我有點沒有看懂，你能把這個實例給解釋一下嗎？
Sample Input
2
1234
2144
1111
9999
Sample Output
2
4
是說1111變成9999隻需要4步嗎？（就是1減1，變成9？不知道我有沒有理解錯？）那1234變成2411怎麼只需要2步？
㈤ ACM求幫助！應該是簡單的貪心演算法類的。誰能幫我敲出代碼
AC代碼，132kb，0ms
記得給分哦~~
#include<iostream>
#include<stdio.h>
using namespace std;
int a[12],n,k,visit[12];
__int64 sum=0;
void dfs(int num,int x,int j)
{
if(num==k)
{
sum+=x;
return;
}
for(int i=1;i<=n;i++)
{
if(!visit[i]&&i>j)
{
visit[i]=1;
if(!x)
dfs(num+1,a[i],i);
else
dfs(num+1,x*a[i],i);
visit[i]=0;
}
}
}
int main()
{
memset(visit,0,sizeof(visit));
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(0,0,0);
printf("%I64d\n",sum);
return 0;
}
㈥ acm必備知識都有哪些
備戰ACM資料
一：知識點
數據結構：
1，單，雙鏈表及循環鏈表
2，樹的表示與存儲，二叉樹（概念，遍歷）二叉樹的
應用（二叉排序樹，判定樹，博弈樹，解答樹等）
3，文件操作（從文本文件中讀入數據並輸出到文本文
件中）
4，圖（基本概念，存儲結構，圖的運算）
數學知識
1，離散數學知識的應用（如排列組合、簡單的圖論，數
理邏輯）
2，數論知識
3，線性代數
4，組合代數
5，計算幾何
二 演算法
1，排序演算法（冒拋法，插入排序，合並排序，快速排
序，堆排序）
2，查找（順序查找，二分發）
3，回溯演算法
4，遞歸演算法
5，分治演算法
6，模擬法
7，貪心法
8，簡單搜索演算法（深度優先，廣度優先），搜索中的
剪枝，A*演算法
9，動態規劃的思想及基本演算法
10，高精度運算
三、ACM競賽的題型分析
競賽的程序設計一般只有16種類型，它們分別是：
Dynamic Programming （動態規劃）
Greedy （貪心演算法）
Complete Search （窮舉搜索）
Flood Fill （不知該如何翻譯）
Shortest Path （最短路徑）
Recursive Search Techniques （回溯搜索技術）
Minimum Spanning Tree （最小生成樹）
Knapsack （背包問題）
Computational Geometry (計算幾何學)
Network Flow （網路流）
Eulerian Path （歐拉迴路）
Two-Dimensional Convex Hull （不知如何翻譯）
BigNums （大數問題）
Heuristic Search （啟發式搜索）
Approximate Search （近似搜索）
Ad Hoc Problems （雜題）
四 ACM競賽參考書
《實用演算法的分析與程序設計》 （吳文虎，王建德著，電子工業出版社，競賽類的黑寶書）
《青少年國際和全國信息學（計算機）奧林匹克競賽指導）――組合數學的演算法
和程序設計》（吳文虎，王建德著，清華大學出版社，參加競賽組合數學必學）
《計算機演算法設計與分析》 （王曉東編著，最好的數據結構教材）
《數據結構與演算法》 （傅清祥，王曉東編著，我所見過的最好的演算法教材）
《信息學奧林匹克競賽指導――1997-1998競賽試題解析》（吳文虎，王建德著，清華大學出版社）
《計算機程序設計技巧》 D.E.Kruth著，演算法書中最著名的《葵花寶典》，大師的作品，難度大）
《計算幾何》周陪德著
《ACM國際大學生程序設計競賽試題與解析（一）》 （吳文虎著，清華大學出版社）
《數學建模競賽培訓教材》 共三本 葉其孝主編
《數學模型》 第二版 姜啟源
《隨機規劃》
《模糊數學》
《數學建模入門》 徐全智
《計算機演算法設計與分析》 國防科大
五 常見的幾個網上題庫
常用網站：
1）信息學初學者之家：http://oibh.ioiforum.org/
（2）大榕樹編程世界：http://www.fjsdfz.org/~drs/program/default.asp
（3）中國教育曙光網：http://www.chinaschool.org/aosai/
（4）福建信息學奧林匹克：http://www.cfcs.com.cn/fjas/index.htm
（5）第20屆全國青少年信息學奧林匹克競賽：http://www.noi2003.org/
（6）第15屆國際青少年信息學奧林匹克競賽：http://www.ioi2003.org/
（7）全美計算機奧林匹克競賽：http://ace.delos.com/usacogate
（8）美國信息學奧林匹克競賽官方網站：http://www.usaco.org/
（9）俄羅斯Ural州立大學：http://acm.timus.ru/
（10）西班牙Valladolid大學：http://acm.uva.es/problemset
（11）ACM-ICPC：http://icpc.baylor.e/icpc/
（12）北京大學：http://acm.pku.e.cn/JudgeOnline/index.acm
（13）浙江大學：http://acm.zju.e.cn/
（14）IOI：http://olympiads.win.tue.nl/ioi/
（15）2003年江蘇省信息學奧林匹克競賽夏令營：http://jsoi.czyz.com.cn
（16）http://acm.zju.e.cn
（17）http://acm.zsu.e.cn
（18）www.shumo.com
（19）http://www.bepark.com/downldmanag/index.asp
（20）http://www.yh01.com colin_fox/colin_fox
五 如何備戰ACM/ICPC
1，個人准備（演算法書，習題集，網上做題和討論）
2，1000題=亞洲冠軍=世界決賽
3，做好資料收集和整理工作
㈦ C語言關於貪心演算法的（很簡單）
LZ在開始研究ACM嘛？
#include
int
least_num_cash(int
_money)
{
/*直接貪心，能用大張的鈔票盡量用大張的*/
int
ret=0;
while(_money!=0)
{
if(_money>=100)
{
_money-=100;
}
else
if(_money>=50)
{
_money-=50;
}
else
if(_money>=20)
{
_money-=20;
}
else
if(_money>=10)
{
_money-=10;
}
else
if(_money>=5)
{
_money-=5;
}
else
if(_money>=2)
{
_money-=2;
}
else
if(_money>=1)
{
_money-=1;
}
ret++;
}
return
ret;
}
int
main()
{
int
n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
printf("%d\n",least_num_cash(m-n));
}
return
0;
}
㈧ ACM題目求解題思路
有N個石子,每個石子重量Qi；按順序將它們裝進K個筐中；求一種方案，使得最重的筐最輕。 分析：本題乍一看很容易想到動態規劃。事實上的確可以用動態規劃解決，稍加分析我們很快得到一個簡單的演算法。用狀態f(i,k)表示將前i個石子裝入k個筐最優方案，g(i,j)表示i-j中最重的石子，則可以寫出狀態轉移方程：g(i,j)=max {g(i,j-1),Qj}f(i,j)=min max {f(k , j-1), g(k+1 , i)} | 1<=j<=k邊界條件：g(i,i)=Qi,f(1,1)=g(1,1)很明顯，這個演算法的時間復雜度為O(N3),空間復雜度為O(N2)，並不十分理想。經過一些優化可以將復雜度降為O(N2)，不過這樣思維復雜度驟然加大，且演算法本身仍不夠高效。現在已經很難在原動態規劃模型上做文章了，我們必須換一個思路。按一般的想法，順序將石子裝入筐，即先把石子放入第一筐，放到一定時候再改放第二個筐，第三個筐……但由於筐的重量沒有上限，我們無法知道放到什麼時候可以停止，轉而將石子放入下一個筐。此時，問題的難點已經顯露出來，是不是有方法可以化解呢？我們不妨針對上面的難點，加入一個參數P，改求一個判定可行解問題：每個筐石子重量和不能超過P，是否可以用K個筐裝下所有石子。首先經過分析不難發現，如果當前筐的石子總重量為T1，即將處理的石子重量為T2，若T1+T2 ≤P，則我們仍將該石子放入當前框，這是顯而易見的。由此可以得出貪心演算法，按順序把石子放進筐，若將石子放入當前筐後，筐的總重量不超過P，則繼續處理下一個石子；若重量和超過P，則將該石子放入下一個筐，若此時筐的數目超過K，則問題無解，否則處理完所有石子後就找到了一個可行解。以上演算法時間復雜度O(N),空間復雜度O(N)，這都是理論的下界。現在我們已經解決了可行解問題，再回到原問題。是不是可以利用剛才的簡化過的問題呢？答案是肯定的。一個最簡單的想法是從小到大枚舉P，不斷嘗試找最優解為P的方案（這就是剛才的可行解問題），直到找到此方案。這就是題目的最優解。估算一下上面演算法的時間復雜度。令T=∑Qi，則最壞情況下需要枚舉T次才能找到解，而每次判斷的時間復雜度為O(N)，因此總的時間復雜度為O(TN)，故需要做進一步優化。下面考慮答案所在的區間。很明顯，若我們可以找到一個總重量不超過P』的解，則我們一定能找到一個總重量不超過P』+1的解，也就是說，可行答案必定可以位於區間[q,+∞]（其中q為本題最優解）。因此，我們自然而然的聯想到了二分，具體方法為：在區間[1,T]內取中值m，若可以找到不超過m的方案，則嘗試區間[1,m-1];若不能，嘗試區間[m+1,T]。不斷重復以上步驟即可找到問題的最優解。分析一下採用二分法後演算法總的時間復雜度：由於每次除去一半的區間，則一共只需判斷log2N次，而每次判斷的時間復雜度為O(N)，因此這個演算法總的時間復雜度為O(NlgT)。一般而言，這個復雜度可以令人滿意的，並且實際使用中效果非常好。但該復雜度同權值有關，不完全屬於多項式演算法，我們可以繼續求得一個多項式演算法（該演算法與本文核心內容無關，只作簡單探討）。首先，此問題的答案必定為某一段連續石子的和，而段數不超過n2，因此，我們最多隻要判斷log2N2=2log2N次即可。現在新的問題是如何找到第m大的段。首先，以每個石子開頭的所有段，例如：3 2 1 2，以2開頭的所有段：2；2 1； 2 1 2， 由於每個石子的重量都大於0，因此總和一定是遞增的。現在有n個遞增段，如何快速的找到第k大的數呢？設各段長度為L1,L2,…,LN,中點分別為M1,M2,…,MN，我們每次詢問各段中點的大小，若L1/2+L2/2+..+LN/2>k，則找到權值最大的中點，刪去其後的數（下圖中紅色部分），否則找到權值最小的中點，刪去其前面的部分（下圖中黑色部分），可以證明刪去的一定不是所求的數。 註：上圖中每個各格子代表一個數。 由以上可知每次可以去掉某一段的1/2，因為有n段，故總共需要去O(Nlog2N)次，每次找最小最大值可以用堆實現，復雜度僅為O(lgN)，因此總的時間復雜度為O(lg2N)，而由上文我們知道找中值的操作總共有log2N次，故這個演算法的時間復雜度為O(Nlg3N)。 至此我們終於得到了一個多項式級別的演算法，當然這個演算法實現起來比較麻煩，實際效果也不甚理想，不過具有一定的理論價值，在此不做過多討論。 回顧本題解題過程，首先我們得到了一個動態規劃演算法，由於很難再提高其效率，因此我們另闢蹊徑，尋求新的演算法。在分析過程中我們發現由於筐的重量沒有上限，因此很難確定將多少石子放入同一個筐內。為了解決此難點，我們加入了參數P，改求可行解問題。參數的加入實際上就是強行給筐定了一個上界。正是由於這無形之中多出的條件，使得問題立刻簡單化，於是我們很自然的得到了貪心演算法。而最終使用二分法降低了演算法的時間復雜度，成功地解決了問題。 由上面的例子我們得到了此類解法的一般步驟，通常分為兩步：Ⅰ.首先引入參數P，解決子問題：能否找到一個不優於P的方案Ⅱ.從小到大枚舉P，判斷是否有優於P的方案，直到找出原問題的最優解 一般地，參數搜索可以通過二分法或迭代降低時間復雜度，由於迭代法證明比較復雜，所以本文更多的討論二分法。 這個方法的應用比較廣泛，通常情況下和上例一樣求最大（小）值盡量小（大）的題目都可以採用此方法，比如下面的例子。神秘的山：有n個隊員攀登n個山峰，每個隊員需要選擇一個山峰，隊員們攀登的山峰各不相同，要求最後一個登頂的隊員用的時間盡量短。 分析：本問題分為兩個部分解決：1．求出每個隊員攀登到各個山峰所需的時間；2．找一個最優分配方案。 第一部分屬於幾何問題，我們可以枚舉每個隊員攀登山峰的位置再做簡單的判斷（題目規定攀登點必須為整點，這就為枚舉提供了條件），這樣就可求得隊員們攀登上各個山峰所需的時間。下面重點討論第二部分。首先將我們的數據構圖，很明顯，我們得到的是一個二部圖，假設有3個隊員3個山峰，每個隊員攀登的時間如下 山峰1山峰2山峰3隊員1132隊員2222隊員3133 則我們可以構圖，每條邊附上相應的權值： 現在的任務就是在圖中找一個匹配，匹配中權值最大的邊盡量小。這個問題是否可以直接套用一些常見的模型呢？比如最大匹配或是最佳匹配？經過分析不難發現在這個問題中它們都是不足以勝任的，因此我們不得不做新的嘗試。 上文提到過要求極大（小）值盡量小（大）的題目往往先定出上界比較容易下手，那麼這題也採用類似的思路。引入一個參數T，先求一個判定可行解的子問題：找一個方案，要求最後登山的隊員所用時間不超過T。 改變後的題目有什麼不同之處呢？如果隊員i攀登上山峰j所需的時間超過T，則可以認為他在規定時間內不能攀登上山峰j，我們就可以把這條邊從圖中刪去。例如在上例中找一個不超過2的方案，經過一次「篩選」，保留的圖如下。 經過這次過濾保留下來的邊都是「合法邊」，我們只需要在這個新的二部圖中找一個完備匹配即可，一個完備匹配唯一對應著一個可行方案。而找完備匹配可以借用最大匹配的演算法，因為如果一個二部圖的最大匹配數等於N，則找到了一個完備匹配，否則該圖中將不存在完備匹配。（上圖中的紅色表示一個完備匹配），那麼這一步的時間復雜度為O(NM)，而在本題中M=N2，因此我們可以在O(N3)的時間內判斷出是否存在一個方案滿足最後等上山頂的隊員時間不超過T。 最後，再用二分法枚舉參數T，找到最優解。由於答案必定為某個隊員攀登上其中一個山峰的時間，因此我們開始的時候可以將所有數據排序，這樣最終的時間復雜度為O(N3lgN)。引入參數後求可行解的子問題與原問題最大的區別在於定下上界以後，我們很自然的排除了一些不可取條件，從而留下了「合法」條件，使得問題變的簡單明了。. 上面的例子在增加了上界之後，排除了一些無效條件，其實它的作用絕不僅局限於此，有些時候，它能將不確定條件變為確定條件，比如下面的例子，最大比率問題：有N道題目,每道題目有不同的分值和難度,分別為Ai,Bi；要求從某一題開始, 至少連續選K道題目,滿足分值和與難度和的比最大。 分析：最樸素的想法是枚舉下標i』,j』，得到每一個長度不小於K的連續段，通過累加Ai』->Aj』，Bi』->Bj』求出比值，並找出比最大的一段。這樣做的時間復雜度很高，由於總共有N2段，每次計算比值的時間是O(N)，則總的時間復雜度到達O(N3)，不過計算比值時，可以採用部分和優化，這樣能把復雜度降至O(N2)，但仍然不夠理想。我們需要追求更出色的演算法，先考慮一個簡單的問題——不考慮難度（Bi），僅僅要求分值和最大（當然此時分值有正有負）。這個簡化後的問題可以直接掃描，開始時為一個長度為K的段，設為Q1,Q2,…Qk， 每次添加一個新數，若Q1+Q2+..+QL-K小於0，則把它們從數列中刪去，不斷更新最優解即可。這樣我們就能在O(N)的時間內找到長度不小於k且和最大的連續段。 之所以能成功解決簡化後的問題，是由於該問題中每個量對最終結果的影響是確定的，若其小於0，則對結果產生不好的影響，反之則是有益的影響。那麼原問題每個參數對最終結果的影響是不是確定的呢？很遺憾，並不是這樣，因為每個題目有兩個不同的參數，他們之間存在著某些的聯系，而這些聯系又具有不確定性，故我們很難知道它們對最終結果是否有幫助。想解決原問題，必須設法消除這個不確定因素！那麼有沒有辦法將這些不確定的因素轉化成確定的因素呢？此時，引入參數勢在必行！那麼我們引入參數P，求一個新的問題：找一個比值不小於P的方案。這個問題實際就是求兩個下標i』,j』，滿足下面兩個不等式j』-i』+1≥k ①(Ai』+Ai』+1....+Aj』)/(Bi』+Bi』+1…+Bj』) ≥ p ②由不等式②=>Ai』+Ai』+1....+Aj』 ≥p(Bi』+Bi』+1…+Bj』)整理得(Ai』-pBi』)+(Ai』+1-pBi』+1)…+(Aj』-pBj』) ≥0可以令Ci=Ai-pBi，則根據上面不等式可知問題實際求一個長度不小於k且和大於０的連續段。由之前的分析可以知道我們能在O(N)的時間內求出長度不小於k且和最大的連續段，那麼如果該段的和大於等於０，則我們找到了一個可行解，如果和小於０，則問題無解。也就是說，我們已經能在O(N)的時間內判斷出是否存在比值不小於P的方案，那麼接下來的步驟也就順理成章了。我們需要通過二分法調整參數P，不斷逼近最優解。計算一下以上演算法的時間復雜度，設答案為T，則該演算法的時間復雜度為O(NlgT)，雖然這並不是多項式級別的演算法，但在實際使用中的效果非常好。引入參數後，由於增加了一個條件，我們就可以將不確定的量變為確定的量，從而解決了問題。三． 總結 本文主要通過幾個例子說明了參數搜索法在信息學中的應用，從上文的例子可以看出加入參數一方面能大大降低思維復雜度，另一方面也能得到效率相當高的演算法，這使得我們解最解問題又多了一中有力的武器。當然，任何事物都是具有兩面性的。參數搜索在具有多種優點的同時也有著消極的一面。由於需要不斷調整參數逼近最優解，其時間復雜度往往略高於最優演算法，且通常依賴於某個權值的大小，使得我們得到的有時不是嚴格意義上的多項式演算法。文章中還總結了使用此方法解題的一般步驟，在實際應用中，我們不能拘泥於形式化的東西，必須靈活應用，大膽創新，這樣才能游刃有餘的解決問題。
㈨ 浙大ACM第2416我用貪心演算法做的為什麼不對，希望高手解答
傳統bfs的題目，貪心不一定對，請問樓主能給出證明嗎
㈩ 求三四個貪心演算法的例題（配源程序代碼，要帶說明解釋的）！非常感謝
貪心演算法的名詞解釋
http://ke..com/view/298415.htm
第一個貪心演算法 （最小生成樹）
http://ke..com/view/288214.htm
第二個貪心演算法 （Prim演算法）
http://ke..com/view/671819.htm
第三個貪心演算法 （kruskal演算法）
http://ke..com/view/247951.htm
演算法都有詳細解釋的