Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Απλή απληστία

        άπληστη μέθοδοςΕίναι ένα είδος λύσηςΠρόβλημα βελτιστοποίησης Αυτή η μέθοδος εξετάζει πάντα τη στρατηγική για την επίτευξη του βέλτιστου (ή καλύτερου) παγκόσμιου αποτελέσματος μετά το τοπικό βέλτιστο (ή καλύτερο) στην τρέχουσα κατάσταση. Προφανώς, εάν υιοθετηθεί μια καλύτερη αλλά όχι βέλτιστη στρατηγική (η βέλτιστη στρατηγική μπορεί να μην υπάρχει ή να μην είναι εύκολο να σκεφτεί κανείς), το συνολικό αποτέλεσμα που προκύπτει δεν μπορεί να είναι βέλτιστο.Για να επιτευχθεί το βέλτιστο αποτέλεσμα, κάθε στρατηγική ενδιάμεσου βήματος απαιτείται να είναι βέλτιστη, επομένως η άπληστη μέθοδος χρησιμοποιείται αυστηρά για την επίλυση του προβλήματος.βελτιστοποίηση της Το ερώτημα απαιτεί αιτιολόγηση της στρατηγικής που υιοθετήθηκε. Η γενική ιδέα της απόδειξης είναι η χρήση απόδειξης μέσω αντίφασης και μαθηματικής επαγωγής, δηλαδή, υποθέτοντας ότι η στρατηγική δεν μπορεί να οδηγήσει στη βέλτιστη λύση και στη συνέχεια να ληφθεί η αντίφαση μέσω μιας σειράς εξαγωγής για να αποδειχθεί ότι η στρατηγική είναι βέλτιστη και, τέλος, χρησιμοποιήστε τη μαθηματική επαγωγή για να εξασφαλίσετε το συνολικό βέλτιστο. Ωστόσο, για καθημερινή χρήση, μπορεί να μην είναι χρόνος ή εύκολο να αποδείξετε αυστηρά τη στρατηγική που σας έρχεται στο μυαλό (η απόδειξη της απληστίας είναι συχνά πιο δύσκολη από την ίδια την απληστία), οπότε γενικά μιλώντας, εάν σκεφτείτε μια στρατηγική που φαίνεται εφικτή, Και αν δεν μπορείτε να δώσετε ένα αντιπαράδειγμα, τότε να είστε αρκετά γενναίοι για να το εφαρμόσετε.

1. Ομαδοποιήστε τον μικρότερο αριθμό

Δεδομένου ενός αριθμού αριθμών από το 0 έως το 9, μπορείτε να τακτοποιήσετε αυτούς τους αριθμούς με οποιαδήποτε σειρά, αλλά πρέπει να τους χρησιμοποιήσετε όλους και να κάνετε τον αριθμό-στόχο όσο το δυνατόν μικρότερο (φυσικά, το 0 δεν μπορεί να είναι ο πρώτος). δύο 0, δύο 1, τρία 5 και An 8, ο μικρότερος αριθμός που προκύπτει είναι 100155858.

---

Πιστεύω ότι μπορείτε να δείτε τη στρατηγική με τη μία: πρώτα επιλέξτε τον μικρότερο αριθμό που δεν είναι 0 από το 1 έως το 9 για έξοδο και μετά εξάγετε τους αριθμούς από το 0 έως το 9. Ο αριθμός των φορών που εξάγεται κάθε αριθμός είναι ο αριθμός που απομένει.

Απόδειξη σωστής στρατηγικής：

• Πρώτα απ 'όλα, δεδομένου ότι όλοι οι αριθμοί πρέπει να συμμετέχουν στο συνδυασμό, καθορίζεται ο αριθμός των ψηφίων στο τελικό αποτέλεσμα.
• Δεδομένου ότι το υψηλότερο bit δεν είναι 0, επιλέξτε έναν αριθμό όσο το δυνατόν μικρότερο όπως το πρώτο bit - το υψηλότερο θεώρημα bit
• Τα υπόλοιπα ψηφία θα πρέπει επίσης να εξάγονται από μικρό σε μεγάλο~

Αυτό στο σχολικό βιβλίο είναι πραγματικά πολύ αφηρημένο και φαίνεται να είναι λίγο λάθος εδώ ο μπλόγκερ έγραψε ο ίδιος:

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

Λογικά δεν είναι δύσκολο, το κυριότερο είναι να σκέφτεσαι καθαρά~

2. Απογραφή Mooncake

• Εισαγωγή: Εισαγάγετε N και M στην πρώτη γραμμή: ο αριθμός των N-ψήφιων τύπων φεγγαρόπιτας και η ζήτηση M-ψηφίων για mooncakes πρέπει να εισαχθούν στις επόμενες δύο γραμμές: οι N αριθμοί στην πρώτη γραμμή αντιστοιχούν τους τρέχοντες τύπους Πόσα μπορείτε να κερδίσετε αφού πουλήσετε όλα τα φεγγαρόπιτα και ο αριθμός N στη δεύτερη γραμμή αντιστοιχεί στον τρέχοντα συνολικό αριθμό των φεγγαρόπιτες~.
• Απαιτούμενη παραγωγή: μέγιστο εισόδημα υπό καθορισμένη ζήτηση

Φανταστείτε αν ήσασταν το αφεντικό, πώς θα ήσασταν «άπληστοι»; Προφανώς - εάν χρειάζεται μόνο να πουλήσετε όσο το δυνατόν περισσότερα mooncakes με την πιο ακριβή τιμή μονάδας εντός της περιορισμένης ζήτησης, δεν θα ήταν δυνατό να συλλέξετε τον μεγαλύτερο τζίρο; Ακολουθεί μια υλοποίηση γραμμένη από τον ίδιο τον blogger, η οποία είναι διαφορετική από αυτή του σχολικού βιβλίου:

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

Δοκιμάστε προσεκτικά τον βρόχο whlie στα παραπάνω: όταν το M δεν είναι 0 - δηλαδή, υπάρχει ακόμα ζήτηση, πουλήστε τα πιο ακριβά mooncakes. Πουλήστε ένα προς ένα με τη σειρά: Εάν η τρέχουσα ζήτηση είναι αρκετή για να πουλήσετε όλους τους τρέχοντες τύπους, η συνολική τιμή θα προστεθεί απευθείας εάν δεν είναι αρκετή για να πουλήσετε όλα τα τρέχοντα, τότε πουλήστε όσα υπάρχουν είναι και υπολογίζονται με βάση την τιμή μονάδας~

Ας το δοκιμάσουμε με τη δοκιμαστική περίπτωση από το σχολικό βιβλίο:

• 3 20
• 18 15 10
• 75 72 45

Το αποτέλεσμα είναι 94,50, το οποίο είναι συνεπές με την τυπική απάντηση~

Επιπλέον, ο blogger εδώ γράφει απευθείας την ταξινόμηση στην κύρια συνάρτηση, τη γράφει σε μια ανεξάρτητη συνάρτηση και στη συνέχεια την καλεί λόγο, μπορείτε να το γράψετε στην περιοχή σχολίων~

2. Διάστημα άπληστοι

Το στέλεχος της ερώτησης έχει ως εξής:

Για αυτού του είδους τις ερωτήσεις, πρέπει απλώς να θυμάστε——Δώστε προτεραιότητα στο διάστημα με το μεγαλύτερο αριστερό τελικό σημείο！

 

Ας μιλήσουμε για το γιατί το κάνουμε αυτό, όπως φαίνεται στην παραπάνω εικόνα: δεν είναι δύσκολο να το βρεις,Για να διασφαλίσουμε όσο το δυνατόν περισσότερες επιλογές, όταν ένα μεγαλύτερο διάστημα περιέχει μικρότερο διάστημα, πρέπει πρώτα να επιλέξουμε το συντομότερο διάστημα, αυτό είναι εύκολο να γίνει κατανοητό.

Για την παραπάνω κατάσταση, όπως τα επικαλυπτόμενα διαστήματα όπως το 1 και το 2, δεν είναι δύσκολο να διαπιστώσετε ότι εάν επιλέξετε το διάστημα 1 με το μεγαλύτερο αριστερό τελικό σημείο, θα καταλαμβάνει μόνο τη θέση 9, ενώ εάν επιλέξετε το διάστημα 2, θα καταλάβει θέση 8. Θέση - Αυτό προφανώς δεν συνάδει με την ιδέα της άπληστης δαπάνης όσο το δυνατόν λιγότερων χρημάτων (δαπανώντας λιγότερο χώρο), επομένως θα πρέπει να επιλέξετε όσο το δυνατόν πιο αριστερά, ώστε να υπάρχουν περισσότεροι κενοί χώροι στα δεξιά ~ όπως παραπάνω,Μπορούμε να δούμε με τον χειροκίνητο υπολογισμό ότι υπάρχουν το πολύ 4 ασύνδετες.

Κωδικός από το σχολικό βιβλίο:

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

Ωστόσο, στους bloggers εξακολουθούν να μην αρέσουν οι αρχικοί πίνακες Ακολουθεί μια έκδοση διανυσματικής δομής:

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

Το τεστ έχει ως εξής:

 

---

Γενικά, η άπληστη μέθοδος είναι μια αλγοριθμική ιδέα που χρησιμοποιείται για την επίλυση ενός τύπου προβλήματος βελτιστοποίησης και ελπίζει να εξαγάγει το παγκόσμιο βέλτιστο αποτέλεσμα από μια τοπική βέλτιστη στρατηγική.άπληστος αλγόριθμος Τα εφαρμοστέα προβλήματα πρέπει να ικανοποιούν τις ιδιότητες της βέλτιστης υποδομής, δηλαδή, η βέλτιστη λύση ενός προβλήματος μπορεί να κατασκευαστεί αποτελεσματικά από τις βέλτιστες λύσεις των υποπροβλημάτων του. Προφανώς δεν είναι όλα τα προβλήματα κατάλληλα για τη μέθοδο greedy, αλλά αυτό δεν εμποδίζει τον άπληστο αλγόριθμο να γίνει ένας απλός, πρακτικός και αποτελεσματικός αλγόριθμος~