Ringkasan "Catatan Algoritma" No. 6

Ringkasan "Catatan Algoritma" No. 6 - Serakah

2024-07-12

1. Keserakahan sederhana

metode serakahIni adalah semacam solusiMasalah pengoptimalan Metode ini selalu mempertimbangkan strategi untuk mencapai hasil global yang optimal (atau lebih baik) setelah hasil optimal lokal (atau lebih baik) pada keadaan saat ini. Jelasnya, jika strategi yang lebih baik namun tidak optimal diadopsi (strategi optimal mungkin tidak ada atau tidak mudah untuk dipikirkan), hasil global yang diperoleh tidak akan optimal.Untuk memperoleh hasil yang optimal maka setiap strategi langkah perantara harus optimal, sehingga metode serakah digunakan secara ketat untuk menyelesaikan masalah tersebut.mengoptimalkan Pertanyaan tersebut membutuhkan pembenaran atas strategi yang diambil. Ide umum dari pembuktian adalah dengan menggunakan pembuktian dengan kontradiksi dan induksi matematis, yaitu dengan asumsi bahwa strategi tersebut tidak dapat menghasilkan solusi yang optimal, kemudian diperoleh kontradiksi tersebut melalui serangkaian derivasi untuk membuktikan bahwa strategi tersebut optimal. , dan terakhir menggunakan induksi matematika untuk memastikan optimal global. Namun, untuk penggunaan sehari-hari, mungkin bukan waktu yang tepat atau mudah untuk membuktikan secara ketat strategi yang terlintas dalam pikiran Anda (pembuktian keserakahan seringkali lebih sulit daripada keserakahan itu sendiri), jadi secara umum, jika Anda memikirkan strategi yang tampaknya layak, Dan jika Anda tidak bisa memberikan contoh tandingan, maka beranilah untuk menerapkannya.

1. Kelompokkan bilangan terkecil

Diberikan sejumlah angka 0 sampai 9, Anda dapat menyusun angka-angka ini dalam urutan apa pun, tetapi Anda harus menggunakan semuanya, dan membuat angka target sekecil mungkin (tentu saja, 0 tidak bisa menjadi yang pertama). dua angka 0, dua angka 1, tiga angka 5, dan An 8, bilangan terkecil yang didapat adalah 100155858.

Saya yakin Anda dapat melihat strateginya sekaligus: pertama-tama pilih angka terkecil yang bukan 0 dari 1 hingga 9 untuk dikeluarkan, lalu keluarkan angka dari 0 hingga 9. Berapa kali setiap angka dikeluarkan adalah angka yang tersisa.

Bukti strategi yang benar：

Pertama-tama, karena semua angka harus ikut serta dalam kombinasi, jumlah digit pada hasil akhir ditentukan.
Karena bit tertinggi bukan 0, pilihlah angka sekecil mungkin seperti bit pertama - teorema bit tertinggi
Digit yang tersisa juga harus dihasilkan dari kecil ke besar~

Yang ada di buku teks terlalu abstrak dan sepertinya agak salah. Di sini blogger menulis sendiri:


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

Logikanya tidak sulit, yang penting berpikir jernih~

2. Persediaan kue bulan

Input: Masukkan N dan M pada baris pertama: jumlah N-digit jenis kue bulan, dan M-digit permintaan pasar terhadap kue bulan; N angka harus dimasukkan dalam dua baris berikutnya: N angka pada baris pertama sesuai dengan jenis saat ini. Berapa banyak yang bisa Anda peroleh setelah menjual semua kue bulan, dan angka N di baris kedua sesuai dengan jumlah total kue bulan saat ini~
Output yang dibutuhkan: pendapatan maksimum berdasarkan permintaan tertentu

Bayangkan saja jika Anda adalah bosnya, bagaimana Anda akan menjadi “serakah”? Tentunya - jika Anda hanya perlu menjual kue bulan sebanyak-banyaknya dengan harga satuan termahal mungkin dalam jumlah permintaan yang terbatas, bukankah bisa mengumpulkan omzet sebanyak-banyaknya? Berikut implementasi yang ditulis oleh blogger sendiri, berbeda dengan yang ada di buku teks:


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

Cicipi dengan cermat lingkaran whlie di atas: ketika M bukan 0 - yaitu, masih ada permintaan, jual kue bulan termahal. Jual satu per satu secara berurutan: Jika permintaan saat ini cukup untuk menjual semua tipe saat ini, maka total harga akan langsung ditambahkan; jika tidak cukup untuk menjual semua tipe saat ini, maka jual sebanyak yang ada adalah dan menghitung berdasarkan harga satuan~

Mari kita uji dengan test case dari buku teks:

3 20
18 15 10
75 72 45

Hasilnya 94,50, sesuai dengan standar jawaban~

Selain itu, blogger di sini langsung menulis pengurutan di fungsi utama, menulisnya di fungsi independen, lalu memanggilnya. Sepertinya ada bug di vektor tipe struktur, dan pengurutan tidak berhasil alasannya, kalian bisa menuliskannya di kolom komentar~

2. Interval serakah

Batang pertanyaannya adalah sebagai berikut:

Untuk pertanyaan seperti ini, kamu hanya perlu mengingat—Berikan prioritas pada interval dengan titik akhir kiri yang lebih besar！

Mari kita bahas mengapa kita melakukan ini, seperti yang ditunjukkan pada gambar di atas: tidak sulit untuk menemukannya,Untuk memastikan sebanyak mungkin pilihan, ketika interval yang lebih panjang berisi interval yang lebih pendek, kita harus memilih interval yang terpendek terlebih dahulu, ini mudah dimengerti.

Untuk keadaan di atas, seperti interval yang tumpang tindih seperti 1 dan 2, tidak sulit untuk menemukan bahwa jika Anda memilih interval 1 dengan titik akhir kiri terbesar, maka hanya akan menempati posisi 9, sedangkan jika Anda memilih interval 2, maka akan menempati posisi 8. Posisi - Hal ini jelas tidak sejalan dengan pemikiran serakah mengeluarkan uang sesedikit mungkin (spending less space), jadi sebaiknya pilih sejauh mungkin ke kiri, agar lebih banyak ruang kosong di sebelah kanan ~ seperti di atas,Kita dapat melihat dengan perhitungan tangan bahwa paling banyak terdapat 4 buah yang saling lepas.

Kode dari buku teks:


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

Namun, blogger masih tidak menyukai array asli. Berikut adalah versi struktur vektor:


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

Tesnya adalah sebagai berikut:

Secara umum, metode serakah merupakan ide algoritmik yang digunakan untuk memecahkan suatu jenis masalah optimasi dan berharap memperoleh hasil optimal global dari strategi optimal lokal.algoritma serakah Masalah yang dapat diterapkan harus memenuhi sifat-sifat substruktur optimal, yaitu solusi optimal suatu masalah dapat dibangun secara efektif dari solusi optimal submasalahnya. Tentunya tidak semua permasalahan cocok untuk metode serakah, namun hal ini tidak menghalangi algoritma serakah untuk menjadi algoritma yang sederhana, praktis dan efisien ~

Berbagi teknologi