復(fù)習(xí)-基礎(chǔ)貪心-創(chuàng)新互聯(lián)

貪心簡介

貪心算法正如其名，貪心，意為每次都選擇一個問題的子問題的最優(yōu)情況，從而達(dá)到整體上的最優(yōu)情況。

創(chuàng)新互聯(lián)服務(wù)項目包括崇明網(wǎng)站建設(shè)、崇明網(wǎng)站制作、崇明網(wǎng)頁制作以及崇明網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，崇明網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到崇明省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

但是貪心算法實際上是比較難用的，因為對于某些問題而言，每次選擇最佳情況，最后不一定會達(dá)到整體上的最優(yōu)情況，比如01背包問題，因為實際上01背包問題的特點就是每個個體是不可拆分的，對于貪心策略而言，必須具備無后效性，即某個狀態(tài)以前的過程不會影響之后的狀態(tài)。

例題1

P2240 【深基12.例1】部分背包問題 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)

對于部分背包問題，因為對于某一個物體，我們可以任意分割，并且其性價比不變，所以我們可以采用貪心算法，對其性價比進(jìn)行排序后，從高到低依次拿取，直到拿完或者背包容量不足。屬于是入門級例題

#include#include#include 
using namespace std;
const int N = 1000;
struct Gold
{
	double w;
	double v;
	double ave;
};

Gold TP[N];

bool cmp(Gold a,Gold b){
	return a.ave >b.ave;
}

int main()
{
	int N, T; cin >>N >>T;
	float res = 0;
	for (int i = 0; i< N; i++)
	{
		cin >>TP[i].w >>TP[i].v;
		TP[i].ave = TP[i].v / TP[i].w;
	}
	sort(TP, TP + N,cmp);
	for (int i = 0; T>0&&i

例題2P1223 排隊接水 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)
本題相比上題難度稍微大一點，但是也屬于基礎(chǔ)題（怎么求平均值稍微花了我一點時間）。因為如果第i人在排隊，那么就同時有n-i人在等待，所以，sum+=(n-i)* V[i].first；貪心策略就不多說了。
#include#include#include 
#includeusing namespace std;
const int N = 1000;
vector>V(N, { 0,0 });
bool cmp(paira, pairb)
{
	return a.first< b.first;
}
int main()
{
	int n; cin >>n;
	double sum = 0;
	for (int i = 1; i<= n; i++)
	{
		cin >>V[i].first;
		V[i].second = i;
	}
	sort(V.begin()+1, V.begin()+n+1,cmp);
	for (int i = 1; i<= n; i++)
	{
		sum += (n-i)* V[i].first;
		cout<< V[i].second<< " ";
	}
	cout<< endl<< fixed<< setprecision(2)<< sum / n;
	return 0;
}
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
            
                標(biāo)題名稱：復(fù)習(xí)-基礎(chǔ)貪心-創(chuàng)新互聯(lián)
                

                網(wǎng)頁URL：http://m.rwnh.cn/article38/ceihpp.html
            
            
                成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、云服務(wù)器、網(wǎng)站建設(shè)、App開發(fā)、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計            
            
                廣告
                
            
            
                聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：
                創(chuàng)新互聯(lián)


        
            猜你還喜歡下面的內(nèi)容
            
                
                            Python正則表達(dá)式和元字符詳解-創(chuàng)新互聯(lián)
                        

                            分布式資源調(diào)度框架Yarn如何理解-創(chuàng)新互聯(lián)
                        

                            基于go手動寫個轉(zhuǎn)發(fā)代理服務(wù)的代碼實現(xiàn)-創(chuàng)新互聯(lián)
                        

                            JavaScript如何求取數(shù)組中非NaN數(shù)據(jù)中的最大值-創(chuàng)新互聯(lián)
                        

                            Hadoop2.4安裝與配置-創(chuàng)新互聯(lián)
                        

                            【蘇小林主頁】基于TP6和光年模板的個人主頁-創(chuàng)新互聯(lián)
                        

                            微信公眾號開發(fā)中如何設(shè)置自定義菜單-創(chuàng)新互聯(lián)

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

復(fù)習(xí)-基礎(chǔ)貪心-創(chuàng)新互聯(lián)