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

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

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

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

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

#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

#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;
}