"Algoritmihuomautukset" yhteenveto nro 6

"Algoritmihuomautukset" yhteenveto nro 6 - Ahne

2024-07-12

1. Yksinkertainen ahneus

ahne menetelmäSe on eräänlainen ratkaisuOptimointi ongelma Tämä menetelmä ottaa aina huomioon strategian saavuttaa optimaalinen (tai parempi) globaali tulos nykytilan paikallisen optimaalisen (tai paremman) jälkeen. On selvää, että jos valitaan parempi, mutta ei optimaalinen strategia (optimaalista strategiaa ei ehkä ole olemassa tai sitä ei ole helppo ajatella), saatu globaali tulos ei voi olla optimaalinen.Optimaalisen tuloksen saavuttamiseksi jokaisen välivaiheen strategian on oltava optimaalinen, joten ongelman ratkaisemiseen käytetään tiukasti ahnetta menetelmää.optimoida Kysymys edellyttää valitun strategian perusteluja. Todistuksen yleinen ajatus on käyttää todistetta ristiriidalla ja matemaattisella induktiolla, eli olettaen, että strategia ei voi johtaa optimaaliseen ratkaisuun, ja saada sitten ristiriita sarjan johdolla todistamaan, että strategia on optimaalinen. , ja lopuksi käytä matemaattista induktiota globaalin optimin varmistamiseksi. Päivittäisessä käytössä ei kuitenkaan välttämättä ole aikaa tai helppoa todistaa tiukasti mieleen tulevaa strategiaa (ahneuden todistaminen on usein vaikeampaa kuin itse ahneus), joten yleisesti ottaen, jos ajattelet toteuttamiskelpoiselta vaikuttavaa strategiaa, Ja jos et voi antaa vastaesimerkkiä, ole tarpeeksi rohkea toteuttamaan se.

1. Ryhmittele pienin numero

Kun numerot ovat 0–9, voit järjestää nämä numerot mihin tahansa järjestykseen, mutta sinun on käytettävä niitä kaikkia ja tehtävä mahdollisimman pieni kohdenumero (0 ei tietenkään voi olla ensimmäinen, esimerkiksi Enter). kaksi 0:ta, kaksi 1:tä, kolme 5:tä ja An 8:a, pienin saatu luku on 100155858.

Uskon, että voit nähdä strategian heti: valitse ensin pienin luku, joka ei ole 0, 1-9 tulostettavaksi, ja tulosta sitten numerot 0-9. Kunkin luvun tulosteiden lukumäärä on sen jäljellä oleva luku.

Todiste oikeasta strategiasta：

Ensinnäkin, koska kaikkien numeroiden on osallistuttava yhdistelmään, lopputuloksen numeroiden lukumäärä määritetään.
Koska suurin bitti ei ole 0, valitse ensimmäiseksi bitiksi mahdollisimman pieni luku - korkeimman bitin lause
Loput numerot tulee myös tulostaa pienistä suuriin~

Oppikirjan teksti on todella liian abstrakti ja näyttää olevan hieman väärä.


#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
 
int main() {	
	vector<int> V;
	for(int i=1;i<=10;i++)
	{
		int temp=0;
		cin>>temp;
		V.push_back(temp);
	}
	sort(V.begin(),V.end());  //直接排成升序 
	int flag=0;  //标记 
	for(int i=0;i<=9;i++)
		if(V[i]!=0)
		{
			int temp=V[i];
			V[i]=V[0];
			V[0]=temp;
			flag=i;//保存第一个不为0的位置 
			break;	
		}
	for(int i=flag+1;i<=9;i++)  //找更小的头，直接从flag下一位开始即可，节省时间~ 
		if(V[i]<V[0]&&V[i]!=0)
		{
			int temp=V[i];
			V[i]=V[0];
			V[0]=temp;
		}
	for(int i=0;i<=9;i++)
		cout<<V[i];
}

Loogisesti se ei ole vaikeaa, tärkeintä on ajatella selkeästi~

2. Mooncake inventaario

Syötä N ja M ensimmäiselle riville: N-numeroinen kuukakkutyyppien määrä ja M-numeroinen markkinakysyntä on syötettävä kahdelle seuraavalle riville: ensimmäisellä rivillä olevat N numerot vastaavat nykyiset tyypit Kuinka paljon voit ansaita kaikkien kuukakkujen myynnin jälkeen, ja toisella rivillä oleva N-luku vastaa nykyistä kuukakkujen kokonaismäärää~.
Vaadittu tuotos: enimmäistulo määrätyllä kysynnällä

Kuvittele vain, jos olisit pomo, kuinka olisit "ahne"? Ilmeisesti - jos vain rajoitetun kysynnän puitteissa pitäisi myydä mahdollisimman monta kuukakkua kalleimmalla yksikköhinnalla, eikö olisi mahdollista kerätä suurinta liikevaihtoa? Seuraava on bloggaajan itsensä kirjoittama toteutus, joka eroaa oppikirjassa olevasta:


#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
 
struct mooncake{
	double num;  //总数 
	double income;  //总收入 
 	double price;   //单价，需要自己计算 
}; 
 
int main() {
	int N,M;
	cin>>N>>M;
	vector<mooncake> V;
	for(int i=1;i<=N;i++) 
	{
		mooncake temp;
		V.push_back(temp);
	}
	cout<<"请输入数量："<<endl;
	for(int i=1;i<=N;i++) 
	{
		double num=0;
		cin>>num;
		V[i-1].num=num;
	}
	cout<<"请输入总价："<<endl;
	for(int i=1;i<=N;i++) 
	{
		double income=0;
		cin>>income;
		V[i-1].income=income;
	}
	for(int i=0;i<=N-1;i++) 
		V[i].price=V[i].income/V[i].num; //计算单价
	//按单价降序排列！保证贵的尽可能多卖
	
	for(int i=0;i<=V.size()-1;i++)
	{
		for(int j=i;j<=V.size()-1;j++)    
			if(V[j].price>V[i].price)    
			{
				mooncake temp;
				temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			}
	}
	for(int i=0;i<=V.size()-1;i++)
		cout<<"单价第"<<(i+1)<<"高的值为："<<V[i].income<<" "<<V[i].price<<" "<<V[i].num<<endl;
	
	
	for(int i=0;i<=N-1;i++)
		cout<<V[i].num<<endl; 
	int j=0;  //使用的下标 
	double count=0;  //总利润 
	while(M>0)  //当还有需求量时 
	{
		double doubt=0;
		doubt=M-V[j].num; //用M减去当前类型的额总量 
		if(doubt>=0)//减了以后M还有剩余
		{
			M-=V[j].num;//当前种类全部卖出 
			count+=V[j].income;//直接总价相加 
			j++;
			cout<<V[j].num;
		}
		else if(doubt<0) //不够减这么多
		{
			count+=V[j].price*M;//剩余部分按照单价计算 
			break; 
		} 
	}
	cout<<"最高利润值为："<<count<<endl;
	return 0;
}

Maista varovasti whlie-silmukkaa yllä olevassa: kun M ei ole 0 - eli kysyntää on vielä, myy kalleimmat kuukakut. Myy yksitellen järjestyksessä: Jos nykyinen kysyntä riittää myymään kaikki nykyiset tyypit, kokonaishinta lisätään suoraan, jos se ei riitä kaikkien nykyisten myymiseen, niin myy niin monta kuin on ovat ja lasketaan yksikköhinnan perusteella~

Testataan sitä oppikirjan testitapauksella:

3 20
18 15 10
75 72 45

Tulos on 94,50, mikä vastaa standardivastausta~

Lisäksi bloggaaja kirjoittaa lajittelun suoraan pääfunktioon, kirjoittaa sen itsenäiseksi funktioksi ja sitten kutsuu sen rakennetyyppisessä vektorissa, ja lajittelu ei onnistu syystä, voit kirjoittaa sen kommenttikenttään~

2. Intervalliahne

Kysymysvarsi on seuraava:

Tämän tyyppistä kysymystä varten sinun tarvitsee vain muistaa...Anna etusija aikavälille, jolla on suurempi vasen päätepiste！

Puhutaanpa siitä, miksi teemme tämän, kuten yllä olevassa kuvassa näkyy: sitä ei ole vaikea löytää,Varmistaaksemme mahdollisimman monta vaihtoehtoa, kun pidempi aikaväli sisältää lyhyemmän välin, meidän on ensin valittava lyhin väli, tämä on helppo ymmärtää.

Yllä olevassa tilanteessa, kuten päällekkäisissä intervalleissa, kuten 1 ja 2, ei ole vaikeaa havaita, että jos valitset intervallin 1, jolla on suurin vasen päätepiste, se on vain paikan 9, kun taas jos valitset intervallin 2, se varaa. Asema 8. Asema - Tämä ei tietenkään ole sopusoinnussa ajatuksen kanssa mahdollisimman vähän rahankäytöstä (vähemmän tilan käyttäminen), joten kannattaa valita mahdollisimman kauas vasemmalle, jotta tyhjää tilaa jää enemmän oikealla ~ kuten yllä,Näemme käsin laskemalla, että hajanaisia on enintään 4.

Koodi oppikirjasta:


#include <cstdio>
#include <algorithm>
using namespace std;
 
const int maxn=110;
struct Inteval{
	int x,y;  //开区间左右端点 
}I[maxn]; 
 
bool cmp(Inteval a,Inteval b)
{
	if(a.x!=b.x)
		return a.x>b.x;   //左端点从大到小排序 
	else
		return a.y<b.y;   //左端点相同的按右端点从小到大排序 
}
 
int main() {
	int n;
	while(scanf("%d",&n,n!=0))
	{
		for(int i=0;i<n;i++)
			scanf("%d%d",&I[i].x,&I[i].y);
		sort(I,I+n,cmp); //排序区间 
		int ans=1,lastX=I[0].x;
		//ans记录总数，lastX记录上一个被选择的区间的左端点 
		for(int i=1;i<n;i++)
		{
			if(I[i].y<=lastX)   //如果该区间右端点在lastX左边 
			{
				lastX=I[i].x;  //以I[i]作为新选中的区间 
				ans++;   //不相交的区间个数+1 
			}	
		}
		printf("%dn",ans);	
	} 
	return 0;
}

Bloggaajat eivät kuitenkaan edelleenkään pidä alkuperäisistä taulukoista. Tässä on vektorirakenneversio:


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct section{
	int x=0;
	int y=0;
	//x和y分别为左右端点 
}; 
 
 
int main() {
	int n=0;
	vector<section> V;
	cin>>n;
	for(int i=1;i<=n;i++) //读入数据 
	{
		section temp;
		int x=0,y=0;
		cin>>x>>y;
		if(x>y)   //防止左端点大于右端点 
		{
			int temp1=x;
			x=y;
			y=temp1;	
		}
		else if(x==y) //若左右端点相同 
		{
			i-=1;  //则当前输入 不算
			cout<<"不可以输入相同的左右端点！"<<endl; 
			continue;  //舍弃数据，本次循环作废~ 
		}	
		temp.x=x;
		temp.y=y;
		V.push_back(temp);
	}
	//按要求排序区间优先级 
	for(int i=0;i<=V.size()-1;i++)
	{
		for(int j=i+1;j<=V.size()-1;j++)
		{
			if(V[j].x>V[i].x)  //左端点越大越靠前
			{
				section temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			}
			else if(V[j].x==V[i].x&&V[j].y<V[i].y) //左端点相同的话，右端点小的优先 
			{
				section temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			} 
		}
	}
	cout<<"顺序如下："<<endl; 
	for(int i=0;i<=V.size()-1;i++)
		cout<<V[i].x<<"~"<<V[i].y<<endl; 
	int count=1,lastX=V[0].x;
	//count用来统计总数，lastX是上一个符合条件的区间的左端点
	 
	for(int i=1;i<=V.size()-1;i++)//直接从第二个区间开始 
	{
		if(V[i].y<lastX)  //如果当前区间的右端点不和上一个左端点相加，满足题意 
		{
			lastX=V[i].x;
			count++;
		}		
	} 
	cout<<count<<endl;
	return 0;
}

Testi on seuraava:

Yleensä ahne menetelmä on algoritminen idea, jota käytetään eräänlaisen optimointiongelman ratkaisemiseen ja joka toivoo saavansa globaalin optimaalisen tuloksen paikallisesta optimaalisesta strategiasta.ahne algoritmi Sovellettavien ongelmien tulee täyttää optimaalisen alirakenteen ominaisuudet, eli sen osaongelmien optimaalisista ratkaisuista voidaan rakentaa tehokkaasti optimaalinen ongelman ratkaisu. Ilmeisesti kaikki ongelmat eivät sovellu ahneelle menetelmälle, mutta tämä ei estä ahneesta algoritmista muodostumasta yksinkertainen, käytännöllinen ja tehokas algoritmi~

Teknologian jakaminen