技術共有

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

1. 単純な貪欲さ

        貪欲な方法それは一種の解決策です最適化問題この方法では、現在の状態での局所的な最適 (またはより良い) の後に、最適 (またはより良い) グローバルな結果を達成するための戦略が常に考慮されます。明らかに、より優れているが最適ではない戦略が採用された場合 (最適な戦略が存在しないか、または考えるのが容易ではない)、得られる全体的な結果は最適ではありません。最適な結果を得るには、各中間ステップ戦略が最適である必要があるため、問題を解決するには貪欲な方法が厳密に使用されます。最適化するこの質問では、採用された戦略の正当性が求められます。証明の一般的な考え方は、矛盾と数学的帰納法による証明を使用することです。つまり、戦略が最適な解決策を導くことができないと仮定し、一連の導出を通じて矛盾を取得し、戦略が最適であることを証明します。 、最後に数学的帰納法を使用して大域最適を確保します。ただし、日常的に使用する場合、思いついた戦略を厳密に証明するのは時間的または簡単ではない可能性があります (貪欲の証明は貪欲そのものよりも難しいことがよくあります)。そのため、一般的に、実現可能と思われる戦略を思いついた場合、反例を提示できない場合は、勇気を持って反例を実行してください。

1. 最小の数をグループ化する

0 から 9 までの数値を指定すると、これらの数値を任意の順序で配置できますが、それらをすべて使用し、ターゲットの数値をできるだけ小さくする必要があります (もちろん、0 を最初の数値にすることはできません)。 0 が 2 つ、1 が 2 つ、5 が 3 つ、および 8 が含まれており、取得される最小の数は 100155858 です。

---

戦略はすぐに理解できると思います。まず 1 ～ 9 の中から 0 以外の最小の数字を選択して出力し、次に 0 ～ 9 の数字を出力します。それぞれの数字が出力された回数が残りの数字になります。

正しい戦略の証明：

• まず、すべての数字が組み合わせに参加する必要があるため、最終結果の桁数が決まります。
• 最上位ビットは 0 ではないため、最初のビットとしてできるだけ小さい数を選択する - 最上位ビット定理
• 残りの桁も小さいものから大きいものへ出力する必要があります~

教科書に載っているものは本当に抽象的すぎて、少し間違っているようです。ここではブロガー自身が書いたものです。

#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.月餅在庫

• 入力: 最初の行に N と M を入力します。N 桁の月餅の種類の数と、M 桁の月餅の市場需要を次の 2 行に入力する必要があります。最初の行の N は次の値に対応します。現在の月餅をすべて売るといくら稼げるか、2行目のNの数字は現在の月餅の総数に対応します~
• 必要な生産量: 指定された需要の下での最大収入

想像してみてください。あなたが上司だったら、どのように「貪欲」になるでしょうか?当然のことですが、限られた需要の中で、できるだけ単価の高い月餅をできるだけたくさん売れば、最も多くの売上を集めることができるのではないでしょうか？以下はブロガー自身が書いた実装であり、教科書のものとは異なります。

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

上記のループを注意深く味わってください。M が 0 でないとき、つまり需要がまだあるとき、最も高価な月餅を売ります。 1 つずつ順番に販売します。現在の需要が現在のタイプをすべて売り切るのに十分な場合は、合計価格が直接追加されます。現在のタイプをすべて売り切るのに十分でない場合は、そこにある数だけ販売します。であり、単価に基づいて計算されます~

教科書のテストケースを使ってテストしてみましょう。

• 3 20
• 18 15 10
• 75 72 45

結果は94.50で、標準の答えと一致しています~

なお、ここのブロガーさんはソートをmain関数に直接書いて、それを独立した関数に書いて呼び出しているのですが、構造体型のベクトルにバグがあるようで、ソートがうまくいきません。理由は、コメント欄に書いてもいいですよ~

2. インターバル貪欲

質問の主旨は次のとおりです。

この種の質問の場合、覚えておく必要があるのは—左側の端点が大きい間隔を優先します。！

 

上の図に示すように、なぜこれを行うのかについて話しましょう。見つけるのは難しくありません。できるだけ多くの選択肢を確保するには、長い間隔に短い間隔が含まれる場合、最初に短い間隔を選択する必要があります。、これはわかりやすいですね。

間隔 1 と 2 などの重複する上記の状況では、左端が最大の間隔 1 を選択すると位置 9 のみを占める一方、間隔 2 を選択すると位置 9 を占めることを見つけるのは難しくありません。位置 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;
}

ただし、ブロガーは依然としてオリジナルの配列を好みません。これはベクトル構造バージョンです。

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

テストは次のとおりです。

 

---

一般に、貪欲法は、一種の最適化問題を解決するために使用されるアルゴリズムのアイデアであり、局所的な最適戦略から全体的な最適な結果を導き出すことを目的としています。貪欲なアルゴリズム適用可能な問題は、最適な部分構造の特性を満たさなければなりません。つまり、問題の最適な解決策は、その部分問題の最適な解決策から効果的に構築できます。明らかにすべての問題が貪欲法に適しているわけではありませんが、だからといって貪欲アルゴリズムがシンプルで実用的かつ効率的なアルゴリズムになることを妨げるものではありません。