貪心演算法磁帶存儲

❶ 貪心演算法 活動安排問題

這道題的貪心演算法比較容易理解，我就不多說明了，只是提到一下演算法思路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注釋我盡力寫了，希望對你有幫助。

❷ 用動態規劃解決矩陣鏈乘法問題時，最優子結構問題是什麼

1、兩種重要演算法思想： 動態規劃，貪心演算法
2、動態規劃：
基本原理：動態規劃英文名dynamic programming。其中pogramming指的是表格法，而非編寫計算機程序。因此，可以初步得出動態規劃的基本思想：將一個具有最優子結構性質的問題分成若干個子問題，在求解過程中，記錄下子問題的結果，存儲在一個表格中，使得公共的子問題只需要計算一次。書中給出的基本原理：動態規劃將問題分成若干個相互重疊的子問題，遞歸的求解子問題，保存子問題的解，再將它們的解組合起來，求出原問題的解。
從基本原理中可以看出動態規劃需要滿足兩個條件，最優子結構和子問題重疊。
最優子結構：書中定義：問題的最優解由相關子問題的最優解組合而成，一個問題的最優解包含其子問題的最優解。典型的有背包問題和鋼條切割我問題。所謂子問題就是一中組合，將一個問題分成許多子問題的集合。某個子問題轉化為問題時，所需要的代價是固定的。
一般這類問題的解題過程：（自己總結）
畫出子問題圖（類似於逆拓撲排序的圖，子問題必須在問題前面完成）
用數學表達式構建出問題的最優解和子問題最優解之間的代數表達式
通常採用自底向上的方法進行遞歸地求解問題的解，自底下上的含義是從最小的子問題求起。
保存每一步求出的子問題的最優解
利用計算出的信息構造一個最優解
3、貪心演算法：
基本原理：從初始狀態出發，每步都經過貪心選擇，最終得到問題的最優解。
含義： 將每一步都看成是當前最佳的選擇，做到局部最優化，直到無法選擇為止。寄希望於局部最優的選擇能夠導致全局最優解。
兩個實例：最小生成樹演算法和單源最短路徑演算法，以及集合覆蓋問題的貪心啟發式演算法。
prim演算法：將集合A看成是一棵樹，每次選擇剩餘的節點中與這棵樹形成的邊的權值最小的點加入到集合A中形成新的樹，循壞調用該過程，知道所有的點都已經放入到集合A中。初始時隨機選擇一個節點放入到集合A中。
kruskal演算法：在所有連接森林中兩顆不同樹的邊裡面，找到權重最小的邊（u，v），並將其加入到集合A中，循環調用該過程，直到所有的點已經放入到集合A中
貪心選擇：當進行選擇時，我們直接作在當前問題看來是最優的選擇，而不必考慮子問題的解。這與動態規劃不同，動態規劃當前問題依賴於較小的子問題。而貪心演算法中做當前問題最優選擇，這樣每步之後只需要做一個子問題的解。
也必須滿足最優子結構的性質，即一個問題的最優解包含其子問題的最優解。
那麼，如何區分什麼時候使用動態規劃，什麼時候使用貪心演算法呢？
典型的兩個問題，0-1背包和分數背包。兩者都具有最優子結構性質，但是貪心演算法只能用來求分數背包的問題，而不能用來求0-1背包的問題。即只有分數背包具有貪心選擇性。
我得總結（不一定對）：具有貪心選擇性的一類問題是：每次做選擇時只有性能不同，而代價是一樣的。那麼這樣每次的選擇都是最好的，最終會得到最好的結果。
哈夫曼編碼也使用貪心選擇演算法。每次選擇待編碼的字元都選擇在剩餘的字元中出現次數最多的

❸ 貪心演算法

平面點集三角剖分的貪心演算法要求三角剖分後邊的總長度盡可能小。演算法的基本思想是將所有的兩點間距離從小到大排序，依次序每次取一條三角剖分的邊，直至達到要求的邊數。以下是兩種貪心演算法的主要步驟。

3.2.2.1 貪心演算法1

第一步:設置一個記錄三角剖分中邊的數組T。

第二步:計算點集S中所有點對之間的距離d(p_i，p_j)，1≤i，j≤n，i≠j，並且對距離從小到大進行排序，設為d₁，d₂，…，d_n(n-1)/2，相應的線段記為e₁，e₂，…，e_n(n-1)/2，將這些線段存儲在數組E中。

第三步:從線段集E中取出長度最短的邊e₁存到T中作為三角剖分的第一條邊，此時k=1。

第四步:依次從E中取出長度最短的邊e_k，與T中已有的邊進行求交運算，如果不相交則存到T中，並從E中刪除e_k。這一步運行到S中沒有邊為止，即至k=n(n-1)/2。

第五步:輸出T。

該演算法中，第二步需要計算n(n-1)/2次距離，另外距離排序需要O(n²lgn)次比較。T中元素隨第四步循環次數的增加而增加，因此向T中加入一條新邊所需要的判定兩條線段是否相交的次數也隨之增加。如果第四步的前3n-6次循環後已經構成點集的三角剖分，那麼第四步循環所需要的判定兩條線段是否相交的次數為

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常數時間內可以判定兩條線段是否相交，因此該演算法的時間復雜性為O(n³)。

3.2.2.2 貪心演算法2

第一步:求點集的凸殼，設凸殼頂點為p₁，p₂，…，p_m，凸殼的邊為e₁，e₂，…，e_m。並將凸殼頂點按順序連接成邊的e_i加入T(三角剖分的邊集合)，並且e_i的權值被賦為1。凸殼內點的集合為S₁={p_m+1，p_m+2，…，p_n}。

第二步:從內部點S₁中任取一點p_i，求與p_i距離最近的點p_j，將線段 存入T。

第三步:求與p_j距離最近的點(除點p_i外)，設為p_k，並將線段 加入T，並將這些邊的權值設為1，而w_ij、w_jk和w_ki的值加1，即為2。邊的權值為2則表示該邊為兩個三角形共有。

第五步:對權值為1的邊(除e₁，e₂，…，e_m外)的兩個端點分別求與其距離最近的點，並將其連線(得到新的三角形)加入T，新三角形邊的權值加1。

第六步:對權值為1的邊重復上一步，當一條邊被使用一次其權值增加1，直到所有邊的權值均為2為止(除e₁，e₂，…，e_m外)。

貪心演算法2中，第一步耗費O(nlgn);第二步需要計算n-1次距離與n-2次比較;第三步求p_k要計算n-2次的距離與n-3次比較;第四步要進行(n-3)×3次的距離計算及(n-4)×3次比較;第五步至多進行n-6次的距離計算與n-7次比較;第六步到第五步的循環次數不超過3n-9;因此整個貪心演算法2的時間復雜性為

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)

❹ 如何用貪心演算法解決磁碟文件最優存儲問題

dp??
方程為
a(fi,fj)=min{(a(fi,fk)+a(fk,fj)),a(fi,fj)}(k=i+1,i+2...j-1);

❺ 貪心演算法(硬幣找零問題)

小Q手上有 n 種不同面值的硬幣，每種硬幣有無限多個。為了方便購物，他希望帶盡量 少的硬幣，但是要能組合出 1 到 m 之間的任意值。輸入的第一行為兩個整數： m 和 n ，他們的意義如題目描述。 接下來的 n 行，每行一個整數，第 i+1 行的整數表示第 i 種硬幣的面值。輸出的最少需要攜帶的硬幣數量，如果無解則輸出 -1 。
50% 的數據： 1<=n<=10 ， 1<=m<=10^3 ；
100% 的數據： 1<=n<=100 ， 1<=m<=10^9 ；

數據量很大，dp不好做，也不好壓縮，應該採用貪心的思路。首先如果沒有面值為 1 的硬幣必定無法滿足要求可以直接輸出 -1 ，接下來考慮貪心策略，設想如果能夠組合出 1 到 5 之間的任何數值，只要一個 6 的硬幣就能組合出 1 到 11 的任意值，既如果當前能夠組合出 1 到 n 的硬幣，再加入一個 n+1 面值的銀幣就能組合出 1 到 n+n+1 的所有面值。所以基本思路就是用一個變數 cur 存儲當前能表示的面值，將硬幣排序，從大往小找到第一個小於等於 cur+1 的硬幣，硬幣數加一同時更新 cur ，當 cur 大於 m 時輸出。

❻ 找零錢問題的貪心演算法

問題描述：
當前有面值分別為2角5分，1角，5分，1分的硬幣，請給出找n分錢的最佳方案（要求找出的硬幣數目最少）
問題分析：
根據常識，我們到店裡買東西找錢時，老闆總是先給我們最大面值的，要是不夠再找面值小一點的，直到找滿為止。如果老闆都給你找分數的或者幾角的，那你肯定不幹，另外，他也可能沒有那麼多零碎的錢給你找。其實這就是一個典型的貪心選擇問題。
問題的演算法設計與實現：
先舉個例子，假如老闆要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數，為了找給我最少的硬幣數，那麼他是不是該這樣找呢，先看看該找多少個25分的， 99／25＝3，好像是3個，要是4個的話，我們還得再給老闆一個1分的，我不幹，那麼老闆只能給我3個25分，由於還少給我24，所以還得給我2個10分的和4個1分。
具體實現
//找零錢演算法
//By falcon
//輸入：數組m，依次存放從大到小排列的面值數，n為需要找的錢數，單位全部為分
//輸出：數組num，對照數組m中的面值存放不同面值的硬幣的個數，即找錢方案