非常詳細的貪心演算法詳解，請耐心看完一遍，絕對能懂！
我先談談我對貪心演算法的認識吧：
我覺得貪心演算法說簡單一點，其實就是一個對單位量大小的排序，舉個很簡單的例子，就比如說你現在背了一個兜要去超市買東西，你要以擁有的錢買商品填滿你的兜，你是不是要考慮你單位的錢（這里的單位的錢可以理解成一塊錢）可以買到的商品的體積的大小，單位的錢買到商品的體積越大越好，當然一般此類問題的時候，都有很多類商品供你選擇，并且商品是有限的，也就是說你不可能把所有的錢全部拿去買一種商品，所以我們遇到此類問題的時候，就可以先對單位錢可以買到的商品體積大小進行排序，然后再從單位錢買到的商品體積最大的開始依次往小的買，這樣我們就可以實作用最小的錢買到最大體積的商品了，
我舉的這個例子是比較簡單并且比較容易理解的貪心思想的例子，下面我就拿航電oj上的一個題來進行示例，
/* 牛腦寨是一個全村600多人的羌族寨子，震后幾天，這里依然能常常聽到隆隆的聲音，那是對面山上石頭不斷滑落的聲音，在完成整個突擊隊的搶修移動基站的任務后，我提著相機開始記錄這里的受創情況，
突然，我的視線里出現一個羌族老人，這讓我無比的震驚，要知道，那是一個極陡的坡，這個佝僂著腰的老人是怎么艱難地爬上來的？她上來做什么？
繼續找，一把散碎的掛面出現在我的眼前，她顫顫巍巍地撈起鋪滿灰塵的掛面，再次流出了眼淚…
看著她仔細地把掛面放進胸前的圍腰里，我頓然感覺到，這是老人在得到外援之前賴以生存的口糧了，如果不是交通中斷，外部救援進不來，老人家又何必拖著80多歲的軀體，強忍失去親人的痛苦，重新回到這奪取她親人生命的廢墟，尋找這點點掛面？老人是真餓了…
老人佝僂著腰，低聲喃喃地念著那兩句話“你們走了，我可怎么活”，拿著那對我們身處城市的人們微不足道的掛面，遠去了…
PS: 拍完這組照片后我才知道，5月14號軍用運輸飛機第一次給汶川空投救援物資就掉在牛腦寨，受災的村民們沒有占為己有，而是汗流浹背地走了兩個小時背到山下的縣城交給政府，
*/---------------------------------------------------------------------------------------------------------
對于幸存的災民來說，最急待解決的顯然是溫飽問題，救災部隊一邊在組織人員全力打通交通，一邊在組織采購糧食，現在假設下撥了一定數量的救災經費要去市場采購大米（散裝），如果市場有m種大米，各種大米的單價和重量已知，請問，為了滿足更多災民的需求，最多能采購多少重量的大米呢？
Input
輸入資料首先包含一個正整數C，表示有C組測驗用例，每組測驗用例的第一行是兩個整數n和m（0<n<=1000,0<m<=1000）,分別表示經費的金額和大米的種類，然后是m行資料，每行包含2個整數p和h(1<=p<=25,1<=h<=100)，分別表示單價和對應大米的重量，
Output
對于每組測驗資料，請輸出能夠購買大米的最多重量（你可以假設經費買不光所有的大米），
每個實體的輸出占一行，保留2位小數，
Sample Input
1
7 2
3 3
4 4
Sample Output
2.33
決議：
這個題目，和我上面說的去超市買商品的例子極其相識，我們要用給定的錢買到最大重量的大米，所以我們要對單位錢可以買到的重量的米（這里已經給出，也就是大米的單價）進行排序，注意這里只對大米單價排序當然還不行，還要考慮到大米的重量，因為這是一一對應的關系，所以我們可以用兩個陣列來分別存大米的單價和大米擁有的重量，然后再根據大米的單價來排序就可以了，或者也可以用結構體來來存大米的單價和重量（此方法寫起來更加簡便），然后直接再進行排序就可以了，最后我們以擁有的經費從單價大的往小的買就可以實作以擁有的經費買到最大的重量了，
下面是我用結構體寫的代碼（也可以試試用兩個一維陣列解決，也不難）：
#include<iostream>
#include<algorithm>
using namespace std;
struct buy{
int p;
int h;
}bou[1001];//定義結構體，p代表單價，h代表重量
bool cmp(buy a,buy b)//定義結構體的排序規則，從大到小
{
return a.p<b.p;
}
int main()
{
int c,n,m;
while(cin>>c)
{
while(c--)
{
double sum=0.0;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>bou[i].p>>bou[i].h;
}
sort(bou,bou+m,cmp);//c++庫函式sort以大米單價進行排序
for(int i=0;i<m;i++)//以單價從大到小購買，并對重量進行累加，經費累減
{
if(n>=bou[i].h*bou[i].p)//當前擁有經費可以把當前單價的大米都買完
{
sum+=bou[i].h;
n-=bou[i].h*bou[i].p;
}
else//當前擁有經費不能把當前單價的大米買完，也就是購買結束
{
sum+=n*1.0/bou[i].p;
break;
}
}
printf("%.2lf\n",sum);
}
}
}
如果覺得對你有用，請點亮"小紅花"~，感謝！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/281611.html
標籤：其他
上一篇：快來學習磁盤磁區